Monotonic Stacks: Next Greater Element

The question: for every element, find the first element to its right that is bigger (-1 if none).

nums   = [2, 1, 5, 3, 4]
answer = [5, 5, -1, 4, -1]

The brute force scans right from every index: O(n²). Notice the waste: while scanning for 2 we walk past 1 and 5, then scan for 1 and walk past 5 all over again.

The idea: walk left to right and keep a stack of indices that are still waiting for their answer. When a new value x arrives, it is the answer for every waiting element smaller than it - pop them all and record x. Then x itself starts waiting.

i  x   pops (answer = x)   stack (values)
0  2   -                   [2]
1  1   -                   [2, 1]
2  5   1 -> 5, 2 -> 5      [5]
3  3   -                   [5, 3]
4  4   3 -> 4              [5, 4]
end: 5 and 4 never answered -> -1

Look at the stack column: the values are always decreasing from bottom to top. If a bigger value sat above a smaller one, it would already have popped it. That ordering is why it's called a monotonic stack, and why we only ever need to look at the top.

Why is it O(n) with a while inside a for? Count the work per index instead of per loop: each index is pushed exactly once and popped at most once. So across the whole run there are at most 2n stack operations. That's an amortized argument: one step might pop many items, but only because earlier steps pushed them.

Variations - same loop, tweak one thing:

• Next smaller: pop while nums[top] > x. The stack is now increasing bottom to top.
• Previous greater / smaller: after popping, whatever is on top (if anything) is the answer for the current index.
• Equal values: < vs <= decides whether a tie counts as "greater". Read the problem carefully.
• Circular array: loop i over range(2 * n) and use nums[i % n].
• Not just arrays: any "who blocks whom" scan, e.g. cars catching up, or bars in a histogram that limit a rectangle's height.