The Monotonic Stack Pattern

[!NOTE] This module explores the core principles of Monotonic Stack, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. Concept Definition

A Monotonic Stack is a stack where the elements are always sorted (either increasing or decreasing). It is the optimal way to solve range query problems like Next Greater Element.

The Problem: Given an array, for each element, find the first number to its right that is larger.

• Naive: Double Loop → O(N²).
• Optimal: Monotonic Stack → O(N).

---

2. Interactive Analysis

Watch how the stack maintains order. We scan the array.

• If current > stack.top, we found the “Next Greater” for the top! Pop and record it.
• Push current element.

Array Input

Monotonic Stack (Decreasing)

Start scanning...

Result: [?, ?, ?, ?, ?, ?]

---

3. Intuition: Amortized Analysis

Wait! There is a while loop inside a for loop. Why is this O(N) and not O(N²)?

The “Aggregate Method” Proof

1. Observation: Every element in the input is Pushed onto the stack exactly once.
2. Observation: Every element can be Popped from the stack at most once.
3. Total Operations: The total number of push operations is N, and the total number of pop operations is at most N.
4. Math: Cost = Sigma(text{pushes}) + Sigma(text{pops}) = N + N = 2N.
5. Complexity: 2N simplifies to O(N).

---

4. Implementation

Java

Go

public int[] nextGreaterElement(int[] nums) {
  int n = nums.length;
  int[] res = new int[n];
  Arrays.fill(res, -1);
  Deque<Integer> stack = new ArrayDeque<>(); // Stores indices

  for (int i = 0; i < n; i++) {
    // While stack not empty and current > top
    while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
      int idx = stack.pop();
      res[idx] = nums[i]; // Found the NGE
    }
    stack.push(i);
  }
  return res;
}

func nextGreaterElement(nums []int) []int {
  res := make([]int, len(nums))
  for i := range res { res[i] = -1 }

  stack := []int{} // Indices

  for i, num := range nums {
    for len(stack) > 0 && num > nums[stack[len(stack)-1]] {
      idx := stack[len(stack)-1]
      stack = stack[:len(stack)-1] // Pop
      res[idx] = num
    }
    stack = append(stack, i) // Push
  }
  return res
}

---

5. Complexity Analysis

Strategy	Time	Space	Notes
Monotonic Stack	O(N)	O(N)	Each element pushed/popped at most once.
Brute Force	O(N^2)	O(1)	Double loop check.