The Monotonic Stack: Remembering Just Enough

"A monotonic stack throws away anything it'll never need again the moment it becomes useless. That ruthless forgetting is what turns an O(n²) 'look ahead' into a single O(n) pass."

The Problem It Solves

Consider: for each element in an array, find the next element to its right that's larger (the "next greater element"). The obvious solution is, for each element, scan rightward until you find a bigger one — O(n²). For a lot of data that's too slow. A monotonic stack solves the whole thing in O(n), and it's one of the most satisfying tricks in this entire quest.

The Idea: Keep the Stack Sorted

A monotonic stack maintains its elements in sorted order — say, decreasing from bottom to top — by popping any element that violates the order before pushing the new one. Here's the magic for "next greater": walk left to right. Before pushing each new value, pop every element on the stack that's smaller than it — because for each of those popped elements, this new value is their next greater element. You've answered them and discarded them in one motion. Anything left on the stack is still waiting for its answer.

Why is this O(n) and not O(n²), given the inner pop-loop? The amortized argument from the Complexity track: each element is pushed exactly once and popped at most once. Total pushes + pops ≤ 2n. The inner loop's total work across the whole run is linear, even though any single step might pop several elements. Counting total operations, not nesting, reveals the O(n).

A monotonic stack stays sorted by popping violators before each push. Each element enters and leaves once, so 'for each item, find the next larger/smaller' problems collapse from O(n²) to O(n). The popped element has just found its answer.

The Family of Problems

Once you recognize the shape, a whole family opens up: next greater / next smaller element, daily temperatures (how many days until a warmer one), stock span (how many consecutive prior days were lower), and the famous largest rectangle in a histogram. They all share one signal: "for each element, find the nearest element in some direction that beats it." When you hear that, reach for a monotonic stack.

Pippa's Confession

The monotonic stack didn't click until Dad reframed the popping: "You're not searching — you're answering and discarding." Each element you pop has, in that instant, found its next-greater. You never look at it again. I'd been thinking of it as a clever search; it's actually a clever forgetting — keeping only the elements still waiting for an answer. That reframe is what made the O(n) feel inevitable instead of magical.

Code

Next greater element in O(n)·python

def next_greater(nums):
    """For each element, the next element to its right that is larger.
    -1 if none. O(n) total with a monotonic (decreasing) stack."""
    result = [-1] * len(nums)
    stack = []                       # holds INDICES, kept decreasing by value
    for i, x in enumerate(nums):
        # x is the 'next greater' for every smaller value waiting on the stack
        while stack and nums[stack[-1]] < x:
            idx = stack.pop()        # this element's answer is x — record & discard
            result[idx] = x
        stack.append(i)              # i now waits for ITS next greater
    return result                    # whatever stays on the stack stays -1

print(next_greater([2, 1, 2, 4, 3]))   # [4, 2, 4, -1, -1]
# 2->4, 1->2, 2->4, 4->none, 3->none.
# Each index is pushed once and popped at most once: O(n) total,
# even though there's an inner while-loop.

Exercise

'Daily temperatures': given a list of daily temps, for each day output how many days you must wait for a warmer day (0 if none ever). Adapt the monotonic-stack code above (store indices, compare temps, record the day-gap when you pop). Then argue why it's O(n) despite the inner while-loop.

Hint

Push indices; when today's temp exceeds the temp at the stack's top index, pop and set result[popped] = today_index − popped_index. O(n) because each day is pushed once and popped at most once — total work ≤ 2n.

The Problem It Solves

The Idea: Keep the Stack Sorted

The Family of Problems

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0