Auxiliary-min stack
Store (value, min-so-far) per push so the minimum pops away with its value.
Top of the min stack is the minimum of everything currently stacked.
01The intuition
Start with what you would do by hand
Design a stack that, besides push and pop, can answer "what is the smallest value currently in the stack?" at any moment, and every operation must be a single step, not a scan.
By hand, when asked for the minimum, you would look through everything in the stack: O(n) per question. Keeping a single "current minimum" variable fails the moment that minimum is popped: you no longer know what the next smallest is, and finding out means a scan again. The problem is not computing the minimum; it is remembering what the minimum was before each push, so that a pop can restore it.
Build the structure, one piece at a time
Piece one: an ordinary stack of values.
Piece two: beside each value, store the minimum of everything at or below it. When you push a value v, the new minimum is min(v, the minimum stored at the old top). So each entry is a pair (value, minSoFar), and computing the second half costs one comparison. You can keep the pairs in one stack or keep a second "min stack" that moves in step with the first; the picture is the same.
| Operation | Value stack (bottom → top) | Min-so-far stack | getMin |
|---|---|---|---|
| push 5 | 5 | 5 | 5 |
| push 2 | 5, 2 | 5, 2 | 2 |
| push 7 | 5, 2, 7 | 5, 2, 2 | 2 |
| push 1 | 5, 2, 7, 1 | 5, 2, 2, 1 | 1 |
| pop | 5, 2, 7 | 5, 2, 2 | 2 |
| pop | 5, 2 | 5, 2 | 2 |
Piece three: pop removes the top of both stacks together. The minimum "pops away with its value", and the entry underneath already holds the correct answer for the smaller stack. No recomputation ever happens.
The idea generalises: store beside each element whatever summary of "everything below me" the query needs. For a max stack it is the maximum so far; for a stack that supports "add k to the bottom i elements" it is a pending increment that is passed down on pop; for "most frequent element" it is a stack per frequency level.
Why it is correct
The invariant: for every position in the stack, the stored minSoFar equals the minimum of all values from the bottom up to that position. It holds for the first push (the only element is its own minimum). For a push of v on top of a position whose stored value m is correct, the new position's minimum is
min(values below and including v) = min(m, v)
which is exactly what we store. A pop removes a position and leaves every other position's stored value untouched, and those values only depended on positions below, which have not changed. So the invariant survives every operation, and getMin, which reads the top's stored value, returns the minimum of the whole current stack.
Why it is fast
push does one comparison and two writes; pop does two removals; getMin does one read. Each is O(1), with no dependence on the stack's size. The cost is memory: one extra number per element, O(n), which is the trade that replaces the O(n) scan. A common refinement stores an entry on the min stack only when a new value is at most the current minimum, which saves space when values mostly increase; pop then removes from the min stack only when the popped value equals its top.
How to recognise it in an interview
Cues: "design a stack with getMin / getMax in O(1)", "support an extra query in constant time", "undo history where you also need an aggregate". The general cue is a stack where a query depends on all current elements, and the fix is to precompute the query's answer for every prefix at push time. Say: "I will store, with each element, the minimum of everything beneath it, so the minimum pops away with its element."
Min Stack is the example. Design a Stack With Increment Operation stores a pending increment per position and passes it down on pop. Maximum Frequency Stack keeps one stack per frequency count and a current maximum frequency, the same "summary beside the element" idea applied to counts.
02The idea in one line
Store (value, min-so-far) per push so the minimum pops away with its value.
Reach for it when: Design: min/max stack, stack with increment, undo histories.
Cost: O(1) per op.
03The walk-through, step by step
The video works one example: Min Stack: push 5, 2, 7, 1; pop; getMin. These are its captions in order, so you can follow without the video or check a step you missed.
- Store the minimum so far beside each value, so pops never need a rescan
- push 5: min so far = min(5, —) = 5
- push 2: min so far = min(2, 5) = 2
- push 7: min so far = min(7, 2) = 2
- push 1: min so far = min(1, 2) = 1
- getMin: read the top of the min stack → 1
- pop: remove 1 and its min entry together
- getMin: read the top of the min stack → 2
- The min stack top is always the minimum of what remains: every op O(1)
04Asked at Google
6 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.
| Problem | Difficulty | Frequency | Reported |
|---|---|---|---|
| Min Stack | Medium | 50 | last 6 months |
| Implement Stack using Queues | Easy | 38 | last 6 months |
| Implement Queue using Stacks | Easy | 34 | last 6 months |
| Design a Stack With Increment Operation | Medium | 26 | |
| Maximum Frequency Stack | Hard | 8 | |
| Max Stack | Hard | 8 |
05Related patterns
Other patterns in Stack: Matching with a stack, Nested structure via stack, Expression evaluation, Collision simulation.