The Monotonic Stack

The question it answers

A family of problems asks, for every element: "where is the next element to my right that is greater than me?" (Or smaller, or the previous one to the left — four symmetric flavors.) Daily temperatures, stock spans, histogram rectangles, sliding-window maxima — all are this question wearing costumes.

Brute force: for each element, scan right until something bigger appears — O(n²) on descending-ish inputs. The fix is a stack with one extra rule, and it computes ALL n answers in one O(n) pass.

The mechanism

Scan left to right, keeping a stack of indices whose answer is still unknown. Maintain one invariant:

The stack's values are strictly decreasing from bottom to top.

Why that invariant survives every step: when element x arrives, anything on top with value < x is popped and answered right there — so whatever is left on the stack after processing x is, by construction, either larger than x or was never compared to it. Nothing smaller can be sitting above something larger, because the moment a smaller element would end up above a larger one, the smaller one gets evaluated against every new arrival and popped the instant something bigger shows up. The invariant isn't assumed — it's enforced fresh by every single push.

When element x arrives, every index on top with value < x has just found its answer — x is the first bigger thing to its right (nothing between them was bigger, or it would have popped them earlier). Pop them, record x as their answer, then push x, which now waits for its bigger thing:

values:  [2, 1, 5, 3]           processing 5:
stack:   [2, 1]   ← 5 arrives   pop 1 (answer: 5), pop 2 (answer: 5)
         [5]      ← push 5      5 waits; 3 arrives, 3 < 5: just push
         [5, 3]   ← end         5 and 3 never found answers: none exist

Think of a monotonic decreasing stack as a row of people's sightlines at a concert: once someone taller stands in front of you, everyone shorter than that person — anywhere between you and them — is now permanently blocked from view and irrelevant to what you can see next. Only progressively taller people ahead of you ever matter again; that's exactly why shorter survivors get popped the moment something bigger arrives, and why what remains on the stack is always decreasing.

def next_greater(nums: list[int]) -> list[int]:
    answer = [-1] * len(nums)          # -1: no greater element exists
    stack: list[int] = []              # indices; values strictly decreasing
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            answer[stack.pop()] = x    # x is their next greater
        stack.append(i)
    return answer

Step through the mechanism on the example above — watch the stack shrink on arrival and the answer row fill in from the pops:

The two arguments you must own

Correctness. When x pops index j, nothing between j and x was greater than nums[j] — anything greater would have popped j already. So x really is j's first greater-to-the-right. And indices still stacked at the end genuinely have no answer: everything after them was smaller (else they'd have popped). The invariant proves both directions.

Cost. The while loop inside a for loop looks quadratic. But each index is pushed exactly once and popped at most once — total pops ≤ n across the entire run. This is whole-execution accounting (Big O's amortized lesson; the same argument as the cancellation scan): bound the sum, not the step. O(n) total, honestly.

Choosing your flavor

Four questions, four settings of two knobs. This course fixes the scan direction at left-to-right for all four and varies only the other two knobs — it's a simplifying convention, not a mathematical requirement; you could equally scan right-to-left and swap which "previous/next" questions read at push versus pop. Holding one knob still keeps the mental model consistent across all four variants, which is the point:

Don't memorize the table — re-derive it each time from the invariant: "what must the stack look like so that the top is exactly the candidate my question needs?" The two problem lessons ahead (Daily Temperatures, Largest Rectangle) each need a different row, and the histogram needs two at once.