The monotonic stack is a waiting room

Most write-ups hand you the loop — push, while-top-is-smaller pop, push again — and trust you to absorb the shape by osmosis. That never worked on me. I could reproduce the loop and still not say what the stack was, which meant I couldn't tell a monotonic-stack problem from one wearing its clothes. This is a sibling to the DP post and to sliding window: the pattern only sticks once you can name the object the loop is maintaining.

The waiting room

Here is the model that finally made it click, and I'm leading with it because everything else falls out of it.

The stack is a waiting room of unresolved elements. An element walks in with a question — "what's the next thing bigger than me?" — and there's no answer yet, so it sits down and waits. More elements walk in with the same question and sit down too. Then an element arrives that answers some of the people waiting: it's bigger than them. So it walks the room, and to everyone it dominates it says "I'm your answer," writes itself into their result, and sends them home. Then it sits down to wait for its own answer.

That's the whole algorithm. The "next greater element" question, the "next smaller," the "how far until a warmer day" — they're all the same waiting room with the domination rule swapped.

Two consequences fall straight out of the model, and they're the two things people get wrong.

First, store indices, not values. The room is full of people, not numbers. You almost always need to know how far apart two elements are — the distance from a waiting element to the one that finally answered it — and you can't recover position from a value. Push the index; read the value with the index when you need it.

Second, the room stays sorted by construction, and you never have to enforce it.

The invariant maintains itself

People treat "keep the stack monotonic" as a chore you perform. It isn't. It's a property that holds automatically given how you decide to push.

Walk the logic. When a new element arrives, you compare it to the top of the stack — the most recent unresolved element. One of two things is true. Either the newcomer resolves the top (it's the answer that top was waiting for), in which case you pop the top, record the answer, and check the new top — repeat until the newcomer no longer resolves anyone. Or the newcomer doesn't resolve the top, in which case it has the same unanswered question the top does, so it sits on top and waits.

Now ask: what does the stack look like after that? You only ever pushed the newcomer once it had stopped resolving the top — which is exactly the condition that makes it sit in monotone order relative to that top. Every element below was placed under the same rule. The order isn't something you maintain; it's the residue of the push decision. You couldn't make the stack non-monotonic without violating the one rule that defines when you're allowed to push.

Next greater element, traced by hand

Take the cleanest case in your own words: for each element of an array, find the next element to its right that is strictly greater; if there is none, the answer is -1. I'll use a stack that holds indices of elements still waiting for a greater neighbor — so the values it points at are decreasing top-to-bottom, which is the "decreasing stack."

The rule: a newcomer x resolves a waiting element w when x > value[w]. So while the top of the stack points at a value less than the newcomer, pop it and record the newcomer as its answer.

Trace it on [2, 1, 2, 4, 3]. I'll show the stack as indices, top on the right, and the answers as they get written.

i=0  v=2   stack empty, nobody to resolve     push 0      stack: [0]
i=1  v=1   top is idx0 (v=2), 1 > 2? no       push 1      stack: [0,1]
i=2  v=2   top is idx1 (v=1), 2 > 1? yes  ->  pop 1, ans[1]=2
           top is idx0 (v=2), 2 > 2? no        push 2     stack: [0,2]
i=3  v=4   top is idx2 (v=2), 4 > 2? yes  ->  pop 2, ans[2]=4
           top is idx0 (v=2), 4 > 2? yes  ->  pop 0, ans[0]=4
           stack empty                          push 3    stack: [3]
i=4  v=3   top is idx3 (v=4), 3 > 4? no        push 4     stack: [3,4]
loop ends  stack: [3,4]  -> these get the default

Notice idx3 (value 4) resolved two waiting elements in one step. That's the waiting room emptying out when the right answer shows up, and it's the entire source of the algorithm's speed.

func nextGreater(_ a: [Int]) -> [Int] {
    var ans = Array(repeating: -1, count: a.count)
    var stack: [Int] = []                  // indices waiting for a greater neighbor
    for i in a.indices {
        while let top = stack.last, a[i] > a[top] {
            ans[stack.removeLast()] = a[i] // newcomer resolves everyone it dominates
        }
        stack.append(i)
    }
    return ans
}

Why it's O(n), spelled out

This is the part that separates having memorized the loop from understanding it, so I'm not going to bury it. The nested while looks like it could be quadratic — a loop inside a loop. It isn't, and the argument is an accounting one.

Charge the cost to elements, not to iterations. Over the entire run, each element is pushed exactly once — one append per index in the outer loop. And each element is popped at most once — once it leaves the stack, it never comes back. So the total number of pops across the whole algorithm is bounded by the total number of pushes, which is n. The inner while can run many times in a single outer step, but only by spending pops that were paid for by earlier pushes. There is no element that gets pushed, popped, and pushed again to be re-examined.

Add it up: n pushes plus at most n pops plus n outer steps. That's O(n) total, amortized — any individual step can be expensive, but the expensive steps are exactly the ones draining work that cheap steps deposited. I worked this accounting out by hand before I trusted it, and I'd recommend doing the same, because "it's a stack so it's fast" is not a reason, it's a vibe.

The leftovers aren't a bug

Here's the panic I want to address head-on, because it cost me real time and it's nearly universal. When the loop ends, the stack is usually not empty. The first time I saw that, I was certain it was a bug — elements left "unchecked," questions I'd failed to answer, some case I'd dropped on the floor.

They are not unchecked. They are precisely the elements for which nothing ever resolved them. An element is still in the waiting room at the end if and only if no later element was ever big enough (or small enough) to be its answer. That's not an omission — that is the answer. The answer to their question is "there is no next greater element," which is exactly what the default value (-1, or nil, or whatever "none" means in your problem) encodes.

Say it plainly: the leftovers aren't a bug, they're the answer to "nothing resolves me." In the trace above, idx3 and idx4 stayed in the stack because no element to their right was greater — and -1 is correct for both. You don't need a special cleanup pass. The default you initialized the result with already says the right thing; the leftovers just never got overwritten.

The boss level: largest rectangle in a histogram

The hardest honest application is the largest rectangle in a histogram: given bar heights, find the largest axis-aligned rectangle that fits under the skyline. The monotonic-stack insight is that for each bar, the widest rectangle of that bar's height extends left and right until it hits a strictly shorter bar — and those two boundaries are exactly "previous smaller" and "next smaller," the two questions a monotonic stack answers.

You keep a stack of indices with increasing heights. When a bar arrives that is shorter than the top, the top has found its right boundary — so you pop it and compute the rectangle that uses the popped bar as its limiting height.

The width arithmetic is the genuinely sharp edge, and I'll be honest: I worked it and never fully locked it in muscle memory. It deserves slow attention, not a hand-wave. When you pop a bar at index top because bar i is shorter, the rectangle's height is heights[top]. The width is the part that bites:

The empty case trips people because there's no left boundary to subtract — the rectangle reaches all the way to the start, so the width is just i. The non-empty case is i - (left boundary) - 1: both boundaries are exclusive, hence the minus one.

The last wrinkle: bars still on the stack when the loop ends have no shorter bar to their right (the leftovers panic again, in a new costume). Rather than write a second loop, append a sentinel bar of height 0 at the end. Being shorter than everything, it forces every remaining bar to pop and get measured, with i sitting at the sentinel's index.

func largestRectangle(_ heights: [Int]) -> Int {
    var best = 0
    var stack: [Int] = []                       // indices of increasing heights
    let bars = heights + [0]                     // sentinel flushes the leftovers
    for i in bars.indices {
        while let top = stack.last, bars[i] < bars[top] {
            let h = bars[stack.removeLast()]
            let w = stack.isEmpty ? i : i - stack.last! - 1  // the sharp edge
            best = max(best, h * w)
        }
        stack.append(i)
    }
    return best
}

When the rest of this series points back to "the stack holds what's unresolved and the right arrival clears it in one sweep," this waiting room is the picture they mean.

Problems to practice