Monotonic stack

You’ll recognise it when

• Every element needs its nearest bigger or smaller neighbour, to the left or to the right.
• The question sounds like “how many days until a warmer day?” or “how far back does this price stay the highest?”
• You need, for each bar, how far it can stretch left and right before hitting a shorter bar (histogram rectangles, “sum of subarray minimums”).
• The obvious answer is a nested loop that scans forward from each element, and n is 10⁵.

It’s often confused with the sliding window maximum, which uses the same trick on a deque because old elements also expire from the front.

The idea

Buildings go up on a street one at a time, from west to east. Each building wants to know the first taller building to its east. When a new one goes up, it settles that question for every shorter building still waiting at the east end of the street. As soon as it meets a waiting building at least as tall as itself, it can stop: every building still waiting further west is at least as tall again, or it would have been answered already.

That’s the whole algorithm. Keep a stack of indices whose answer isn’t known yet. When a new value arrives, it is the first bigger value for every smaller value on top of the stack, so pop them and record the answer. Then push the new index, because it’s waiting too. The stack stays sorted, with values going down from bottom to top, which is where the name comes from.

How it works

We’ll solve next greater element: for each index, the first value to its right that is strictly bigger, or -1 if there is none.

Scroll through the steps and the graphic follows along. Bars are the array, the row under them is ans, and the lane at the bottom is the stack, bottom on the left. You can also press play, or edit the input: try equal values, or a decreasing run followed by one big number.

Why it’s correct: the stack always holds exactly the indices so far that haven’t seen a bigger value, and their values never increase from bottom to top. So the smaller values are all on top, and a new value pops precisely the indices it answers. Each pop happens at the first bigger value to the right, because anything earlier would have popped it already.

def next_greater(a):
    """ans[i] = the first value to the right of a[i] that is bigger, or -1."""
    n = len(a)
    ans = [-1] * n
    stack = []  # indices still waiting for an answer; their values decrease
    for i in range(n):
        while stack and a[stack[-1]] < a[i]:
            top = stack.pop()
            ans[top] = a[i]
        stack.append(i)
    return ans

#include <vector>
using namespace std;

// ans[i] = the first value to the right of a[i] that is bigger, or -1.
vector<int> nextGreater(const vector<int>& a) {
    int n = a.size();
    vector<int> ans(n, -1);
    vector<int> stack;  // indices still waiting for an answer; their values decrease
    for (int i = 0; i < n; i++) {
        while (!stack.empty() && a[stack.back()] < a[i]) {
            int top = stack.back(); stack.pop_back();
            ans[top] = a[i];
        }
        stack.push_back(i);
    }
    return ans;
}

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

class NextGreater {
    // ans[i] = the first value to the right of a[i] that is bigger, or -1.
    static int[] nextGreater(int[] a) {
        int n = a.length;
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        Deque<Integer> stack = new ArrayDeque<>();  // indices still waiting; their values decrease
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && a[stack.peek()] < a[i]) {
                int top = stack.pop();
                ans[top] = a[i];
            }
            stack.push(i);
        }
        return ans;
    }
}

The stack holds indices, not values. You need the index to know which ans slot to fill, and many variations need positions to measure distances or widths.

Why it’s O(n)

There’s a while inside a for, so it looks quadratic. Count per index instead of per loop: every index is pushed exactly once and popped at most once. Across the whole run the while loop body runs at most n times in total, however the pops are spread out. A single step can pop many, but only elements that earlier steps pushed. That’s an amortised O(1) per element.

Space is O(n): ans, plus a stack that holds every index on decreasing input.

Common mistakes

stack.append(a[i])   # ✗ which ans slot does this belong to?
stack.append(i)      # ✓ the value is always a[i]

while stack and a[stack[-1]] <= a[i]:   # ✗ for "strictly greater"
while stack and a[stack[-1]] < a[i]:    # ✓

if stack and a[stack[-1]] < a[i]:      # ✗ pops at most one
while stack and a[stack[-1]] < a[i]:   # ✓ pops everything it beats

Variations

• Next smaller, previous greater, previous smaller. Flip the comparison to find smaller values. For the previous neighbour, the answer is whatever is on top of the stack right after you finish popping, just before you push i.
• Daily temperatures. Store the distance instead of the value: ans[top] = i - top, the number of days top waited.
• Stock span. For each day, count how many days back the price stayed at or below today’s. Pop while price[top] <= price[i]; the span is i minus the index left on top (or i + 1 if the stack is empty).
• Largest rectangle in a histogram. Keep heights increasing. When bar top is popped by a shorter bar at i, it can’t reach i, and it couldn’t reach past the new top on the left either, so its widest rectangle is a[top] * (i - stack[-1] - 1). A height-0 sentinel at the end flushes the stack.
• Sliding window maximum. Keep a decreasing deque of indices. The back works like this stack; the front also drops indices that have slid out of the window. The front is then the maximum of the window, in O(n) total.