Monotonic stack, explained with a queue at a chai stall

Problem: for every element in an array, find the first element to its right that is greater than it. If none, -1.

Brute force: for each i, scan right until you find something bigger. O(n²). With n = 10^5 you are done for.

The chai stall

Imagine people standing in a line outside a chai stall, all looking to the right. Each person wants to know: who is the first person to my right who is taller than me?

Walk along the line from left to right. Keep a stack of people who are still waiting for their answer. Notice something: the people on the stack are always in decreasing order of height from bottom to top. Why? If a shorter person were below a taller one, the taller one would already have answered the shorter one when he arrived.

Now a new person arrives. Everyone on top of the stack who is shorter than him just found their answer: him. Pop them all. Then he joins the stack and waits for his own answer. That is the whole algorithm.

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

Let us dry run on [2, 1, 5, 3, 4].

• i=0 (2): stack empty, push. Stack values [2]
• i=1 (1): 2 is not smaller than 1, push. Stack values [2, 1]
• i=2 (5): pop 1, its answer is 5. Pop 2, its answer is 5. Push. Stack [5]
• i=3 (3): push. Stack [5, 3]
• i=4 (4): pop 3, its answer is 4. 5 is not smaller, stop. Push. Stack [5, 4]

Answer: [5, 5, -1, 4, -1]. Whatever is left on the stack never found a taller person, so -1.

People see a while loop inside a for loop and panic about O(n²). Look again: every index is pushed once and popped at most once. That is at most 2n operations. O(n).

(Not my board. Mine has more chai stains.)

Same idea, different questions

• Daily temperatures: store i - index instead of the value. Days to wait.
• Stock span: you want the previous greater element. After popping everything smaller or equal, whatever is on top of the stack is the answer.
• Largest rectangle in histogram: keep an increasing stack. When you pop a bar, you finally know how far it can stretch on both sides.

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];       // height 0 at the end flushes the stack
        while (!st.isEmpty() && h[st.peek()] > cur) {
            int height = h[st.pop()];
            int left = st.isEmpty() ? -1 : st.peek();
            best = Math.max(best, height * (i - left - 1));
        }
        st.push(i);
    }
    return best;
}

On [2, 1, 5, 6, 2, 3] this returns 10 (the 5 and 6 bars, width 2, height 5). Dry run it yourself, it is worth the 10 minutes.

The three questions to ask before you code

1. Next or previous?
2. Greater or smaller?
3. Strict or not? (This is where duplicates break your solution.)

Next means you resolve answers when you pop. Previous means the answer is whatever is on top after popping. Greater means a decreasing stack, smaller means an increasing stack. Samjhe? Bas itna sa concept hai.

Time: O(n). Space: O(n) for the stack.