Introduction to Monotonic Stack

A monotonic stack is a stack that a caller keeps sorted (increasing or decreasing, bottom to top) by popping any elements that would break the order before pushing — because each element is compared against, and permanently removes, only the elements it beats, the total number of comparisons across the whole array is bounded by the number of pushes plus pops, giving O(n) instead of the O(n²) of comparing every pair.

Recognize the pattern

• The phrase "next/previous greater (or smaller) element" for every index.
• You need, for each element, the nearest element to its left/right satisfying an order relation.
• Histogram / "largest rectangle", "trapping rain water", "stock span", "daily temperatures" — anything reducible to nearest-bigger/smaller-neighbor.
• A naive solution is a double loop comparing each element against all others in one direction.

Brute force → optimal

Brute force: for each index i, scan rightward (or leftward) until you find the first element satisfying the relation. Worst case (strictly decreasing array, looking for next greater) every scan runs to the end: O(n²) time, O(1) extra space.

Optimal (monotonic stack): walk the array once, maintaining a stack of indices whose values are still "undecided" (no next-greater found yet), kept in decreasing order of value from bottom to top. For each new value, pop every stacked index whose value is smaller — the new value IS their answer. Then push the current index. O(n) time, O(n) space.

Complexity, derived

Let n = array length. Each index is pushed onto the stack exactly once (in the single left-to-right pass) and can therefore be popped at most once over the whole run — it never gets pushed again after popping. So total pushes = n, total pops ≤ n. The while-loop body inside the for-loop runs once per pop, so summed over all iterations the inner loop body executes ≤ n times, not n times per outer iteration. Total work = O(n) pushes + O(n) pops = O(n) time. The stack holds at most n indices → O(n) space (plus the O(n) output array).

Worked example — Next Greater Element

Array: [2, 1, 2, 4, 3]. Find next greater element to the right for each index; stack holds indices, kept so values are decreasing bottom→top.

End of array: remaining stack indices [3,4] get NGE = -1 (none found). Final: [4, 2, 4, -1, -1].

Java — Next Greater Element

int[] nextGreater(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    Arrays.fill(res, -1);
    Deque<Integer> stack = new ArrayDeque<>(); // holds indices
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
            res[stack.pop()] = nums[i];
        }
        stack.push(i);
    }
    return res;
}

Pitfalls

• Storing values instead of indices — you then can't report position or distance (e.g. "daily temperatures" needs i - stack.pop()).
• Off-by-one on the comparison operator: < vs <= changes whether equal elements pop each other, which matters for problems needing the strictly next greater/smaller vs. tie-breaking rules.
• Forgetting to drain the stack after the loop — leftover indices need a documented fallback answer (commonly -1).
• Confusing which direction you scan: next-greater-to-the-right needs a left-to-right pass; previous-greater-to-the-left needs the same pass but stack semantics answer a different query per element.

When to use / when not — trade-offs

Use a monotonic stack when the problem needs, for every element, the nearest element in one direction satisfying an order relation — it turns O(n²) pairwise comparison into O(n). Compare with alternatives:

• Sliding window / two pointers: better when the invariant is about a contiguous range's sum/count, not an order relation between elements — monotonic stack does not track sums.
• Sorting + index mapping: works for some "find element with property X" problems but destroys original order, so it can't directly answer "next" queries; also costs O(n log n).
• Segment tree / sparse table (range max): handles arbitrary range-max queries and updates, but is O(n log n) to build and overkill when you only need the single nearest greater neighbor per element, which the O(n) stack answers directly.
• Monotonic deque: when the extreme must also expire out of a sliding FIFO window (window max/min), you need eviction at both ends — that's the monotonic deque, not a plain stack.

Takeaways

• The stack stays ordered because every push first evicts elements that the new value dominates, giving amortized O(n) since each index is pushed and popped at most once.
• Store indices, not values, so you can compute distances or write into a results array by position.
• Increasing stack → find next/previous smaller; decreasing stack → find next/previous greater (the popped elements are the ones "defeated" by the incoming element).

Recall: Why is the total runtime O(n) even though there's a while-loop nested inside a for-loop?

Pattern popularized through LeetCode's Next Greater Element / Daily Temperatures / Largest Rectangle in Histogram problem family; complexity argument via amortized analysis (aggregate method), as in CLRS Ch. 17.