Min Stack: The Augmented Stack That Makes getMin O(1)

Min Stack is a design problem, not a compute problem. You're not asked to find an answer once — you're asked to build a data structure where every operation, including "what's the minimum right now?", runs in constant time, forever, no matter how the caller interleaves pushes and pops.

That last requirement is the trap. Tracking a minimum while values only arrive is trivial: one variable. The moment pop() enters the picture, that variable breaks — pop the minimum off the stack and your single variable has no idea what the previous minimum was.

The fix is one of the most reusable ideas in data-structure design: snapshot the derived state at every depth, so undoing an operation automatically restores it. Get this reframe and Min Stack goes from "clever trick" to obvious.

The problem#

Design a stack that supports push(val), pop(), top(), and getMin() — retrieving the minimum element — with all four operations in O(1) time.

The example shows exactly why this is hard: after pop() removes -3, getMin() must instantly answer -2 — a value that used to be the minimum before -3 arrived. Whatever you build has to remember minimum history, not just the current minimum.

The brute force baseline#

Keep a plain stack and compute the minimum on demand:

push, pop, and top are fine, but every getMin() walks the entire stack — O(n) per call. A workload with n pushes followed by n getMin() calls costs O(n²) total. The problem statement explicitly demands O(1) for every operation, so this fails the spec, not just the style points.

The tempting shortcut — cache the minimum in one variable — fails differently. It answers getMin() in O(1) right up until someone pops the minimum itself. Now the cache is stale, and rebuilding it means rescanning the stack: you've just moved the O(n) from getMin to pop.

The key insight: snapshot the min at every depth#

This is the Augmented Stack pattern. Instead of storing bare values, store each value together with the minimum of everything at or below it:

Each pair's second slot answers the question "if the stack ended here, what would the minimum be?" Computing it at push time is O(1): the new min is just min(val, previous top's min) — the previous pair already summarizes everything below it.

Now watch what pop() does for free. Removing the top pair removes its min snapshot with it, and the pair underneath already holds the correct minimum for the remaining stack. Pop (-3, -3) and the new top is (0, -2) — the old minimum -2 resurfaces with zero recomputation. Undo the push, and the derived state undoes itself.

getMin() collapses to a single read: the top pair's min field. No scan, no bookkeeping, no special cases.

The optimal solution#

This is the exact code the Min Stack visualizer steps through:

Three details carry the whole design:

• The empty-stack guard in push. The first pushed value is its own minimum; only later pushes compare against the previous top's cached min ([1] — the min slot, not the value slot).
• pop() is one line. No min repair, no scanning. The snapshot below the popped pair is already correct — that's the entire payoff of augmenting.
• top() and getMin() read the same pair, different slots. Index 0 is the value, index 1 is the running minimum.

Walkthrough#

The classic operation sequence, pair by pair:

Step 5 → 7 is the whole problem in miniature. The -3 snapshot never had to be "rolled back" — it was physically attached to the entry that left. What remains was correct all along.

Complexity#

The augmented stack stores two numbers per entry instead of one — still O(n), with a constant factor of 2. That constant is the entire price of turning getMin() from a scan into an array read. (A diff-encoding variant can shave the extra slot, but the pair version is the interview-clean answer.)

Common mistakes#

• Comparing the new value against the top's value instead of its min. The cached min at [1] summarizes the whole stack below; the value at [0] is just one element. Compare against the wrong slot and a sequence like push(1), push(5), push(3) caches min=3 — wrong, the real min is 1.
• Keeping one global min variable. It works until pop() removes the minimum, and then you either return stale answers or rescan. The per-depth snapshot exists precisely because a single variable can't remember history.
• Forgetting the empty-stack guard in push. Reading this.stack[this.stack.length - 1][1] on an empty stack throws. The first push must use val as its own min.
• Skipping the snapshot when the value isn't a new minimum. Every push writes a pair, even when the min is unchanged. Record only "new minimums" and the bookkeeping falls out of lockstep — the classic failure is duplicates: push 0 twice, record it once, pop once, and the min record is gone while a 0 still sits in the stack.
• Trying to repair the min inside pop(). If you find yourself recomputing anything on pop, the design is wrong. Correct augmentation makes pop a pure removal.

Where this pattern shows up next#

Min Stack is the cleanest introduction to stacks that carry extra state, and the neighboring problems build straight on it:

• Remove Outermost Parentheses — the gentlest stack-thinking warm-up: tracking nesting depth is a stack collapsed into a counter.
• Evaluate Reverse Polish Notation — the stack as a workspace, where entries hold partial results instead of cached minimums.
• Next Greater Element I — the monotonic stack, where the ordering invariant of the stack itself encodes the answer.
• Daily Temperatures — the monotonic stack at full power, resolving pending questions the moment their answer arrives.

To watch the pairs stack up and the old minimum resurface on pop, step through it interactively — try the duplicate-minimums test case and confirm getMin() survives the first pop.

FAQ#

How does Min Stack achieve O(1) getMin?#

By storing a snapshot of the running minimum with every entry. Each push stores the pair [value, min(value, previous top's min)], so the top pair's min slot always equals the minimum of the entire stack. getMin() is a single array read, and pop() stays O(1) because removing an entry removes its snapshot with it — the pair underneath already holds the correct minimum for what remains.

Why can't I just keep a single min variable?#

Because a single variable can't remember history. It answers getMin() correctly until the minimum itself gets popped — then the variable is stale, and finding the previous minimum requires scanning the remaining stack, making pop() O(n) in the worst case. The augmented stack sidesteps this by recording the minimum at every depth, so the previous minimum is already sitting one entry down.

Do I need two separate stacks to solve Min Stack?#

No. The two-parallel-stacks version (values in one, running minimums in the other) and the pair-per-entry version are the same algorithm with different memory layout — both O(1) per operation and O(n) space. The pair version is harder to get wrong: a value and its min snapshot can never desynchronize, while two stacks must be pushed and popped in lockstep on every operation.

What are the time and space complexity of Min Stack?#

All four operations — push, pop, top, getMin — run in O(1) time. Space is O(n) for n stacked elements, with a constant factor of 2 because each entry stores a value plus its cached minimum. The naive alternative keeps O(1) space overhead but pays O(n) per getMin() scan, which the problem statement explicitly rules out.

How does Min Stack handle duplicate minimum values?#

Automatically, because every push writes its own snapshot. Push 0 three times and the stack holds three pairs, each caching min = 0. Pop one and the next pair still says 0 — correct, since two zeros remain. Duplicates only break the optimized variants that try to record a minimum once instead of per-entry; the pair-per-entry design has no such edge case.