The Monotonic Stack Pattern

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.

1. The Problem: Next Greater Element

Given an array [2, 1, 5, 6, 2, 3]. For each element, find the first number to its right that is larger.

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

---

2. The Mathematical Anchor: 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).

This is why monotonic patterns are so powerful—they transform what looks like a quadratric search into a linear pass.

---

3. Interactive: NGE Visualizer

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: [?, ?, ?, ?, ?, ?]

4. Implementation

Java

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;
}

Go

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
}

In the next chapter, we will see how stacks power the calculators in our pockets.