4.8.0 — Stack & Monotonic Stack: The Pattern

Recognition cue, part one — the plain stack. The problem involves nesting, undoing, or matching pairs. Brackets, expression evaluation, backtracking state.

Recognition cue, part two — the monotonic stack. The problem asks for the nearest greater or smaller element on one side, or for a span, or for a distance to some future event. The brute force is a nested loop that scans forwards or backwards from each position.

The one sentence

A monotonic stack computes on eviction, not on insertion.

Everything difficult in this group dissolves once you hold that. When an item is popped, both of its boundaries are known: the item that triggered the pop is the nearest smaller-or-larger element on one side, and whatever is left on top of the stack is the nearest on the other side. Neither is known before the pop, which is why trying to compute at push time feels impossible.

The templates

# 1. Plain stack — nesting and matching
stack = []
for c in s:
    if is_opener(c): stack.append(c)
    else:
        if not stack or stack.pop() != partner(c): return False
return not stack

# 2. Monotonic stack — next greater to the right
stack = []                      # indices, values DECREASING
for i, v in enumerate(nums):
    while stack and nums[stack[-1]] < v:      # ← flip this comparison
        j = stack.pop()
        answer[j] = i - j                     # ← compute HERE, at the pop
    stack.append(i)

The two things that change between problems are the comparison and the direction of travel:

you want	comparison	direction
next greater to the right	top < current	left to right
next smaller to the right	top > current	left to right
next greater to the left	top < current	right to left
next smaller to the left	top > current	right to left

Derive this once by asking what makes an item on the stack useless, rather than memorising it.

The seven problems

#	Problem	The one insight
4.8.1	Valid Parentheses ★	Nesting means the most recent opener must match first
4.8.2	Min Stack ★	Remember the minimum per level, not globally
4.8.3	Evaluate RPN	An operator consumes the two most recent results
4.8.4	Generate Parentheses ★	Backtracking: never build an invalid prefix
4.8.5	Daily Temperatures	Keep only the days still waiting, in decreasing order
4.8.6	Car Fleet	Sort by position, then count increases in arrival time
4.8.7	Largest Rectangle in Histogram	Every rectangle has a shortest bar; ask how far it reaches

★ marks the Blind 75 subset.

The traps on this pattern

Trying to compute at push time. The right boundary is not known yet. Compute at the pop.

Storing values instead of indices. If the answer is a distance or a width, you need positions.

Forgetting the leftover stack. Items still on the stack at the end never found their match. Either initialise the answer array to the right default, or push a sentinel value that flushes everything through the normal path — a 0 for histograms, an infinity for minimum problems.

< versus <=. Decide whether equal values should evict each other. For Daily Temperatures, "warmer" is strict, so use <. For Min Stack, duplicate minima each need their own entry, so use <=.

Integer division. Python's // floors, so -13 // 5 is -3 when RPN needs -2. Use int(a / b). In Car Fleet, integer division destroys fractional arrival times entirely — use /.

list.pop(0) as a queue. O(n) in Python. Use collections.deque.

What the interviewer will push on

"Why is a monotonic stack O(n) when there is a loop inside a loop?" Each index is pushed exactly once and popped at most once, so the total work is 2n. This is asked on every problem in the group.

"Derive the width formula in Largest Rectangle." Right boundary is the bar that triggered the pop, left boundary is the new stack top, and the rectangle spans strictly between them: right - left - 1.

"Why <= in Min Stack?" Duplicate minima. Give the [2, 2] example.

"What is the sentinel for?" To force the remaining stack to be resolved through the same code path instead of a second loop.

"Change this to find the next smaller element instead." Flip the comparison. Answering instantly shows you understand the structure rather than the problem.

One thing to volunteer: state the eviction rule as a sentence before writing code. "An item is useless once a later item makes it unable to ever be the answer, so it leaves the stack — and that is the moment I can compute its result."

Recall

• Plain stack = nesting, matching, undo. Monotonic stack = nearest greater or smaller element, spans, distances.
• Compute on eviction, not on insertion. At the pop, the triggering item is one boundary and the new stack top is the other.
• Store indices when the answer is a distance or width.
• Two knobs change between problems: the comparison and the direction of travel.
• A sentinel at the end (0 for histograms) flushes the stack through the normal path and removes the cleanup loop.
• O(n) because each index is pushed once and popped once — 2n operations in total.
• Min Stack needs <= so duplicate minima each get an entry. RPN needs int(a/b), not //. Car Fleet needs float division.

Next: 4.8.1 Valid Parentheses — the plain stack at its simplest, and the problem that shows why counting is not enough.