Monotonic Stack

Monotonic Stacks are a specialized use of the stack data structure where elements are maintained in a sorted order (either strictly increasing or decreasing). This powerful technique allows you to solve “Next Greater Element” and “Previous Smaller Element” type problems in O(N) linear time, where a naive approach would take O(N²).

Real-World Analogy

Imagine a line of people waiting to enter a concert. You want to find the next person taller than you in the line to your right.

You look at the person directly in front of you.
If they are shorter, they can’t block your view of anyone taller, effectively “disappearing” from your concern regarding who is the next tall person for the people behind you.
If they are taller, they are the “next greater” person.

A Monotonic Decreasing Stack works similarly: we maintain a list of people in decreasing height order. When a new, taller person arrives, they “pop” (remove) all shorter people from the list because those shorter people now have found their “next greater” element (the new person).

Visual Explanation

Let’s visualize finding the Next Greater Element for the array [2, 1, 5, 6, 2, 3]. We use a decreasing stack because we want to keep elements that haven’t found a greater element yet.

  graph TD
    subgraph "State: Processing 5"
    S1["Stack: 2, 1"] -- "Next is 5 (Greater than 1)" --> P1["Pop 1"]
    P1 -- "Next is 5 (Greater than 2)" --> P2["Pop 2"]
    P2 -- "Stack Empty" --> Push5["Push 5"]
    end

    subgraph "State: Result Map"
    R1["1 -> 5"]
    R2["2 -> 5"]
    end

    style S1 fill:#f9f,stroke:#333
    style Push5 fill:#9f9,stroke:#333

Push 2: Stack is [2].
Push 1: 1 < 2, so it respects the decreasing order. Stack is [2, 1].
Process 5:
- 5 > 1: Pop 1. (Next Greater for 1 is 5).
- 5 > 2: Pop 2. (Next Greater for 2 is 5).
- Stack is empty. Push 5. Stack is [5].
Process 6: 6 > 5. Pop 5. Push 6. Stack is [6].
…and so on.

The stack preserves the “candidates” for the next greater element.

When to Use This Pattern

Use a Monotonic Stack when your problem fits these criteria:

You need to find the next greater or next smaller element for items in an array.
You need to find the previous greater or previous smaller element.
The problem involves finding boundaries for rectangles in histograms or trapping rain water.
You need to optimize a nested loop solution that looks for the “nearest” value satisfying a condition from $O(N^2)$ to $O(N)$.
The problem involves finding the lexicographically smallest/largest subsequence (e.g., Remove K Digits).

Complexity Analysis

The beauty of the monotonic stack is that it processes each element exactly twice: once when it’s pushed, and once when it’s popped.

Time Complexity:
O(N)
- Every element is pushed onto the stack exactly once.
- Every element is popped from the stack at most once.
- Therefore, the total operations are proportional to $N$.
Space Complexity:
O(N)
- In the worst case (e.g., a sorted array), the stack might hold all $N$ elements before any are popped.

Common Mistakes

Wrong Direction: Confusing whether to iterate from left-to-right or right-to-left. (Usually, iterating right-to-left is easier for “Next Greater to the Right” if you want to push results directly, but left-to-right with a stack of indices is more common).
Wrong Monotonicity: Using an increasing stack when you need a decreasing one.
- Next Greater: Use Decreasing Stack.
- Next Smaller: Use Increasing Stack.
Storing Values instead of Indices: Often, you need the distance (index difference) between elements (e.g., Daily Temperatures). Storing indices allows you to access both the value nums[i] and the position i.
Empty Stack Access: Always check if the stack is empty before peeking or popping to avoid runtime errors.

Next Steps

Code Templates: Get the standard boilerplate code for Next Greater/Smaller elements in 6 languages.
Practice Problems: Test your skills on LeetCode problems ranging from Easy to Hard.