Patterns / Stack & Monotonic Stack

Stack & Monotonic Stack Pattern

A stack tracks the most recent relevant element; a monotonic stack answers "next greater/smaller" in linear time.

What it is

A stack (LIFO) is the right tool whenever the most recently seen item is the one you need next — matching brackets, evaluating expressions, undo histories. A monotonic stack adds an invariant: it keeps its elements in increasing or decreasing order by popping anything that would violate that order. Each pop resolves a "next greater" or "next smaller" relationship, so a whole class of problems that look quadratic become a single linear pass.

When to use it — the signals

• Balanced brackets, parsing, or "valid sequence" checks.
• "Next greater / next smaller element" or "days until warmer".
• Spans, histograms, or stack-based simulation (undo/redo).

How it works

A representative implementation in Java:

// Next greater element to the right for each index.
int[] res = new int[nums.length];
Arrays.fill(res, -1);
Deque<Integer> stack = new ArrayDeque<>();   // holds indices, values decreasing
for (int i = 0; i < nums.length; i++) {
    while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
        res[stack.pop()] = nums[i];
    }
    stack.push(i);
}
return res;

Complexity

O(n) — each element is pushed and popped at most once. Space is O(n).

Common pitfalls

• Storing values when you actually need indices (or vice versa).
• Choosing the wrong monotonic direction for the question.
• Forgetting to handle elements left on the stack at the end.

Practice problems

Classic problems where this pattern is the intended approach: Valid Parentheses, Daily Temperatures, Next Greater Element, Largest Rectangle in Histogram. Work through them on the Leet Study home page.