Monotonic Stack

At a glance

The instinct

The brute force for "next greater element" checks every element to the right, giving O(n²). The monotonic stack notices that once a taller element arrives, every shorter element still waiting to its left has found its answer and can leave. What stays behind is always sorted - a staircase of candidates. Each index is pushed once and popped once, so the whole scan is O(n), even with a while loop inside the for.

Recognise it

Not this pattern if...

• You need the max/min of every fixed-size window - that is a monotonic deque (elements also expire from the front).
• You need the k-th largest, or values far away rather than the nearest qualifying one - think heap or sorting.
• Matching brackets or evaluating expressions - that is the plain stack pattern; nothing needs to stay sorted.

Memory hack

Rule of thumb for which way the stack is sorted:

• Looking for the next greater -> keep a decreasing stack (pop smaller ones).
• Looking for the next smaller -> keep an increasing stack (pop bigger ones).
• "Popped elements get their answer from the newcomer; the newcomer gets its previous answer from whatever is left on top."

Say it out loud in the interview:

1. "Do I need greater or smaller, and to the left or right?"
2. "So my stack is increasing/decreasing, storing indices so I can measure distances."
3. "When I pop, I record the popped index's answer; after the loop, leftovers get the default."

How it works

Iterate left to right. Before pushing index i, pop every index whose value loses to a[i]; for each popped index, i is its next greater (or smaller) element. Then push i. Whatever is still on the stack at the end has no answer.

Trace for Daily Temperatures, [73, 74, 75, 71, 69, 72, 76] (decreasing stack of indices):

Index 6 stays on the stack, so its answer is 0.

For Largest Rectangle in Histogram, use an increasing stack. When bar j is popped by a shorter bar at i, i is its right limit and the new stack top is its left limit, so its widest rectangle has width i - top - 1. Appending a sentinel bar of height 0 flushes everything at the end.

flowchart TD
    A[For each index i] --> B{"Stack not empty and a[top] loses to a[i]?"}
    B -- yes --> C[Pop j, answer for j comes from i]
    C --> B
    B -- no --> D[Previous answer for i is the current top, if any]
    D --> E[Push i]
    E --> A

Java template

import java.util.*;

class MonotonicStack {
    // Template 1: next greater element to the right (index distance; 0 if none).
    static int[] nextGreaterDistance(int[] a) {
        int n = a.length;
        int[] ans = new int[n];
        Deque<Integer> st = new ArrayDeque<>();          // indices, values strictly decreasing
        for (int i = 0; i < n; i++) {
            while (!st.isEmpty() && a[st.peek()] < a[i]) { // flip to > for next smaller
                int j = st.pop();
                ans[j] = i - j;                          // or a[i] for the value itself
            }
            st.push(i);
        }
        return ans;                                      // leftovers keep the default 0
    }

    // Template 2: increasing stack + sentinel for "widest span under each bar".
    static int largestRectangle(int[] h) {
        int n = h.length, best = 0;
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = 0; i <= n; i++) {
            int cur = (i == n) ? 0 : h[i];               // sentinel flushes the stack
            while (!st.isEmpty() && h[st.peek()] >= cur) {
                int height = h[st.pop()];
                int left = st.isEmpty() ? -1 : st.peek(); // nearest smaller on the left
                best = Math.max(best, height * (i - left - 1));
            }
            st.push(i);
        }
        return best;
    }

    // Template 3: online previous-greater with aggregated counts (stock span).
    static class Spanner {
        private final Deque<int[]> st = new ArrayDeque<>(); // {price, span}
        int next(int price) {
            int span = 1;
            while (!st.isEmpty() && st.peek()[0] <= price) span += st.pop()[1];
            st.push(new int[]{price, span});
            return span;
        }
    }
}

Complexity

The nested while looks quadratic, but every index enters and leaves the stack at most once, so total pops <= n.

Variations

• Next greater, value or distance - Next Greater Element I (with a hash map for the lookup array), Daily Temperatures.
• Previous greater with aggregation - merge popped spans into the current one: Online Stock Span.
• Nearest smaller on both sides - width of the bar's reach: Largest Rectangle in Histogram, Maximal Rectangle.
• Count what you pop - pops are people you can see: Number of Visible People in a Queue (scan from the right).
• Right-to-left with a tracked threshold - popped values become the best "middle" candidate: 132 Pattern.
• Circular arrays - loop i from 0 to 2n - 1 and use i % n: Next Greater Element II.
• Greedy lexicographic removal - Remove K Digits, Remove Duplicate Letters.
• Contribution counting - each element is the min of left * right subarrays: Sum of Subarray Minimums.

Common mistakes

• Storing values instead of indices, then being unable to compute distances or widths.
• Choosing the wrong monotonic direction - write down "next greater = decreasing stack" before coding.
• Forgetting leftovers: elements still on the stack need a default answer (-1, 0, or a width that reaches the end).
• In the histogram, computing width as i - j instead of i - left - 1, where left is the new top after the pop.
• Using a fixed-window max problem with a stack - when old elements expire from the front, you need a deque.

All practice problems

6 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.