The undo pile,
and its sorted cousin

A stack is a pile with one rule: you may only touch the top. push puts something on, pop takes the most recent thing off, both in O(1) — constant time, no matter how tall the pile. In Python it's a plain list; in Scala, a List whose head is the top. There is nothing to implement. The skill is noticing when a problem is one.

The recognition principle: stacks appear wherever structure nests. An opened bracket must close before the bracket that opened earlier. An undo must revert the most recent edit first. A function call must return before its caller can. That last one matters beyond this chapter — the call stack is literally this data structure, which is why recursion in Chapter 11 is “just DFS with the call stack doing the bookkeeping.”

Put differently: whenever “the most recent unfinished thing” is the only thing you're allowed to care about, a stack is the whole solution. Everything else in this chapter is that sentence with props.

Valid Parentheses Easy is the hello-world of stacks, and probably the single most-asked warm-up in industry. Given a string of ()[]{}, is every bracket closed by the right partner in the right order? Counting openers and closers is not enough — ([)] has matched counts and is still garbage. Order is the point, and order-of-nesting is LIFO.

The algorithm: walk the string once. Opener → push it. Closer → it must match the top of the stack (the most recent unclosed opener); pop on a match, reject on anything else. At the end, the stack must be empty — leftovers mean unclosed openers. Build a string below and watch the pile do the work:

Two Mediums extend the plain pile, and both test design more than algorithms.

Min Stack Medium asks for push, pop, top, and getMin — all O(1). The trap answer is “keep a min variable”, which dies the moment the minimum gets popped: what's the min now? The fix is to make every entry carry its own answer: push pairs (value, min-so-far). Popping automatically restores the previous minimum, because the previous entry remembered it. No recomputation, ever.

Evaluate Reverse Polish Notation Medium: evaluate ["2","1","+","3","*"] → 9. Numbers push; an operator pops two operands, applies, and pushes the result. That's it — postfix notation exists precisely so that a stack can evaluate it with no parentheses and no precedence rules. One gotcha earns real points: the pops come out backwards. For − and /, the first pop is the right operand: b = pop(); a = pop(); push(a − b). (And LeetCode's version truncates division toward zero — Python's // floors, so int(a / b) it is.)

Now the headliner. Consider the question “for each element, where is the next greater element to its right?” Brute force checks every element against everything after it: O(n²) — n scans of up to n elements, dead on arrival for n ≈ 10⁵ (Chapter 3's budget math). The monotonic stack does it in one pass, and the idea fits in a sentence:

Keep a stack of elements still waiting for their answer — and keep it sorted by evicting anyone your new element beats.

Walk left to right. Each new element looks at the top of the stack. If the new element is bigger, then it is the top's answer — the top has been waiting for exactly this — so pop the top, record its answer, and check the new top too. Keep popping until the top is bigger (or the stack is empty), then push the new element to wait its own turn. The stack is always sorted in decreasing order — not because you sort it, but because anything that would break the order gets popped the instant its answer arrives.

Two things fall out of this, both interview gold:

• A pop is a question answered. Every element is pushed exactly once and popped at most once, so the total work across the whole array is at most 2n operations — O(n), guaranteed, despite the nested-looking while loop.
• The direction is configurable. Next greater → keep the stack decreasing (pop while top < new). Next smaller → keep it increasing (pop while top > new). “Previous” instead of “next” → same pass; the answer is read at push time (whatever survives below you is your previous greater/smaller) instead of at pop time. One skeleton, four problems.

You've already brushed against this machine: Sliding Window Maximum Hard from Chapter 6 uses a monotonic deque — the same evict-the-losers pile with a second exit at the bottom so old elements can retire when the window slides past them.

Daily Temperatures Medium is the pattern's flagship: given daily temperatures, answer for each day how many days until a warmer one. Recast it and the tell lights up — each day wants its next greater element to the right, measured in distance.

So: a stack of day indices (indices, not values — you need i − j for the distance), kept decreasing by temperature. Cooler day arrives → it can't answer anyone → push it; the pile of waiting days grows. Warmer day arrives → it pops every colder day off the top, stamping each one's answer as it goes. Days still on the stack at the end never got a warmer day: answer 0. Step through it:

Car Fleet Medium is the pattern in a trench coat. Cars at various positions drive toward a target at various speeds; a fast car that catches a slower one can't pass — it slows down and they become one fleet. How many fleets arrive?

The costume is physics; the pattern is two moves you already own. First, Chapter 7's opener: sort the cars by starting position, closest-to-target first. Second, reduce each car to one number — its solo arrival time, (target − position) / speed. Now walk the sorted cars and keep a stack of fleet leaders' arrival times:

• If my arrival time is ≤ the time on top of the stack, I catch the fleet ahead before the target — I merge into it. No push. (My time is discarded: a fleet moves at its leader's time, and blocked cars can't make it faster.)
• If my time is greater, I never catch them — I'm the leader of a new fleet. Push.

The stack stays strictly increasing in arrival time, and its final height is the answer. That's a monotonic stack where the “pop” degenerated into “don't bother pushing” — same invariant, same one-pass shape, O(n log n) total because the sort dominates the walk.

Largest Rectangle in Histogram Hard is a top-tier interview problem, and it's this pattern's final form. Given bar heights, find the largest rectangle that fits inside the histogram. The key reframe: every candidate rectangle is some bar stretched sideways as far as its height allows — left until a shorter bar blocks it, right until a shorter bar blocks it. So for each bar we need its nearest shorter neighbor on each side. “Nearest shorter” — that's this chapter's tell, twice.

The one-pass version keeps an increasing stack of bar indices. While heights climb, push — everyone's still stretching. The moment a bar arrives that's shorter than the top, the top's stretching days are over, and here is the beautiful part — the pop resolves both walls at once:

• The right wall is the arriving bar — the first shorter bar to the right. That's what triggered the pop.
• The left wall is whatever sits below the popped bar on the stack — the nearest bar shorter than it on the left (anything between them was taller and already got popped). Empty stack → the rectangle stretches to the left edge.

So a pop yields width = i − left, area = height[j] × width, and a shot at the record. Run it and watch for the width-resolution moment on each pop:

Recognition summary for the whole chapter, in two questions. Does the structure nest? Brackets, undo, nested decoding, matched pairs → plain stack; resolve everything against the most recent unfinished item. Does every element seek its nearest dominating neighbor in one direction? Next/previous greater/smaller, days-until, span-of, nearest-shorter → monotonic stack; choose the sort direction so that the interesting arrival forces pops, and read answers off the pops.

And one disqualifier to keep you honest: if the problem wants the max over a sliding range rather than a nearest neighbor, you need the deque variant (Chapter 6); if it wants the k-th largest or a running median, no stack discipline survives — that's heap country, Chapter 14.

The pattern, as a whiteboard skeleton:

1. 1Say the invariant out loud: “the stack stays decreasing” (next greater) or “increasing” (next smaller) — pick the order the arriving element is allowed to break.
2. 2Initialize answer to the “never found” default (0 / −1 / n) and an empty stack of indices — indices buy you distances and widths; values don't.
3. 3For each index i, left to right (flip the direction for “previous …” variants).
4. 4While the stack is non-empty and the new element beats the top: pop j and resolve j's answer from i and j — this pop is the answer happening.
5. 5Push i to wait for its own answer.
6. 6Settle the survivors: leftovers keep the default — or append a sentinel value that force-pops everyone (the histogram's height-0 bar).
7. 7Name the costs unprompted: O(n) time — each index pushed once, popped at most once — and O(n) stack space worst case.
8. 8Check the equality edge: decide whether ties pop (strict < vs ≤) and test on a run of equal values before declaring victory.

The flagship, both ways. The brute force re-scans the future for every day — O(n²), and you should still say it in the room; it's your safety net and your baseline. The pattern inverts the question: instead of each day searching forward for its answer, each warm day arriving hands answers backward to the cold days piled up waiting. Same information flow, opposite direction, and the re-scan disappears.

Read the delta: the inner scan becomes a while-pop, and the answers get written at pop time. That delta — let the future resolve the parked past — is the entire monotonic-stack family: swap the comparison and the resolve line, and this exact function becomes Next Greater Element, stock spans, or the histogram's wall-finder.