Matching, Undo & Design Stacks

A stack is last-in, first-out (LIFO): the most recent item you pushed is the first one you get back. Reach for one whenever a problem has the feel of processing the latest one first: the most recent unclosed bracket, the last character typed, the last score recorded. With a little extra state per entry, a stack can also answer questions like "what is the minimum right now?" in $O(1)$ .

The idea#

Many string and simulation problems have nested or "undo" structure. In all of them, the thing that decides what happens to the current item is the most recent unresolved item, which is exactly the top of a stack.

Situation	Push	On the current item
Matching pairs (brackets, tags)	each opener	a closer must match the popped top
Undo / backspace	each kept item	an undo token pops the top
Cancel adjacent pairs	each item	if it equals or cancels the top, pop instead of pushing
Collisions	survivors so far	resolve against the top in a loop until stable

Each item is pushed and popped at most once, so all of these run in $O(n)$ .

So far each entry is a plain item. A design stack goes one step further and stores extra state in each entry. The entry records a fact about everything beneath it, so the fact is still correct after any pop.

How to spot it#

The latest item decides what to do with the current one. Look for these signals.

Brackets, tags, or anything that opens and closes and can nest.
"Remove adjacent duplicates" or "backspace" where a removal can expose a new match (Candy Crush style).
An operation that refers to "the previous" or "the last two" results.
A design question asking for get_min, get_max or "most frequent" in $O(1)$ on top of push and pop.

Template#

This is the matching shape. The cancel, undo and collision shapes change only what happens when the current item meets the top.

stack = empty
for each item in input:
    if item closes or acts on earlier work:
        if stack is empty: fail or skip    # nothing to match
        top = pop from stack
        if top does not fit item: fail     # wrong match
    else:
        push item
if stack is not empty: fail                # leftovers never closed
succeed

Notice the three ways to fail: a closer with nothing open, a closer of the wrong type, and openers left over at the end.

Pitfalls#

Most broken stack solutions come down to one of these.

Popping an empty stack. Check stack before stack.pop() or stack[-1] whenever the input can be malformed.
Forgetting the final check. Input like "((" never fails a match. Only the leftover check catches it.
Using if instead of while when one item can resolve many. One incoming item can pop several entries in a row.
Over-engineering design stacks. An entry that looks stale is often exactly right for a later pop. Check before you add cleanup code.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with Valid Parentheses.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Valid Parentheses

Map each closer to its opener. Push openers; on a closer, the popped top must be its opener. Return not stack at the end.

Hint: Remove All Adjacent Duplicates In String

If the character equals the top, pop; otherwise push. A removal can expose a new pair, and the next character checks it automatically.

Hint: Backspace String Compare

Build each string with a stack where # pops (if anything is there). Then compare the two stacks with ==.

Hint: Baseball Game

Numbers push, C pops, D pushes double the top, and + pushes the sum of the top two. The answer is sum(stack).

Hint: Min Stack

For each entry, store its value and the minimum up to that point: (val, min(val, previous_min)). Then get_min is the top's second field, and popping restores the old minimum for free.

Hint: Minimum Remove to Make Valid Parentheses

Keep a ) only if an unmatched ( exists. Any ( still unmatched at the end is extra. Drop those scanning from the right, because the rightmost ones have no closer after them.

Hint: Asteroid Collision

Only a positive top with a negative incoming asteroid collides; every other sign pair is pushed. On a collision the smaller one explodes, and equal sizes destroy both. Resolve in a while loop, because one asteroid can destroy several.

Hint: Longest Valid Parentheses

Push (char, index). When a ) matches a ( on top, mark both indices as valid. The answer is the longest run of consecutive marked indices: one stack pass plus one linear scan.

Hint: Maximum Frequency Stack

Keep freq[val] and a stack per frequency, group[f]. Push adds val to group[freq[val]]; pop takes from group[max_freq]. A value lives in several groups at once, and that's correct: its copy in group 1 is the one to pop next at frequency 1.

Hint: Implement Queue using Stacks

Push onto an "in" stack. Pop from an "out" stack, and refill it from "in" only when it's empty. Each item moves at most once, so operations are amortized $O(1)$ .

Hint: Implement Stack using Queues

With one queue: after appending a new item, rotate the queue len - 1 times so the new item comes to the front. Then pop and top read from the front.

Key takeaways#

If the latest unresolved item decides what happens next, use a stack.
Matching fails three ways: nothing to match, wrong match, leftovers at the end.
Push indices when you need positions, not only values.
Store extra state in each entry (running min, frequency group) for $O(1)$ queries.

Core idea#

Use a stack when the most recent unresolved item decides what happens to the current item. Extra state in each entry gives $O(1)$ queries such as get_min.

Key points#

Each item is pushed and popped at most once, so these problems run in $O(n)$ .
Matching fails three ways: a closer with nothing open, a closer of the wrong type, openers left at the end.
Push indices when you need positions, not only values.
Spot it: brackets or tags that nest, "remove adjacent duplicates", "backspace", "the previous result", get_min in $O(1)$ .

Situations#

Situation	Push	On the current item
Matching pairs	each opener	a closer must match the popped top
Undo / backspace	each kept item	`#` or `C` pops the top
Cancel adjacent pairs	each item	equal to the top: pop instead of push
Asteroid collisions	survivors	only `+` top vs `-` incoming collide; resolve in a `while`

Design stacks and other tricks#

Min Stack: push (val, min(val, previous_min)). The top's second field is the minimum.
Maximum Frequency Stack: keep freq[val] and a stack per frequency. Pop from group[max_freq]. Leave old copies in lower groups.
Queue from two stacks: push to "in"; pop from "out", and refill it only when empty. Amortized $O(1)$ .
Longest Valid Parentheses: mark matched indices, then find the longest run of marks.
Minimum Remove to Make Valid: drop unmatched ( from the right.

Template#

stack = empty
for each item in input:
    if item closes earlier work:
        if stack is empty: fail            # nothing to match
        if pop from stack does not fit item: fail
    else:
        push item
return stack is empty                      # leftovers never closed

Pitfalls#

Popping an empty stack. Check stack before pop() or stack[-1].
Forgetting the final not stack. "((" never fails a match.
if instead of while for collisions. One asteroid can pop many.
Over-engineering Maximum Frequency Stack. Old copies are correct where they are.

Say it in an interview#

"The latest unresolved item decides what happens next, so use a stack."
"Each entry stores the minimum up to that point, so get_min is O(1)."