Min Stack
Design a stack that reports its minimum in O(1) by storing the minimum alongside every value
Problem Statement
Design a stack supporting push, pop, top and getMin, where every operation runs in O(1) time.
push(-2) → stack: [-2] getMin() = -2
push(0) → stack: [-2, 0] getMin() = -2
push(-3) → stack: [-2, 0, -3] getMin() = -3
getMin() → -3
pop() → stack: [-2, 0]
top() → 0
getMin() → -2 ← the minimum went back UP after the popIntuition
push, pop and top are trivial on any stack. getMin is the whole problem.
Scanning the stack on each call is O(n). Caching a single min variable is O(1) for push — but breaks on pop.
Why one cached minimum is not enough
Push -2, 0, -3. The cached minimum is -3. Now pop.
The minimum must revert to -2 — but that value is gone from the cache and you would have to rescan the stack to recover it. A single variable cannot remember history, and pop moves backwards through history.
The key insight
Store, alongside each value, the minimum of the stack at the moment that value was pushed.
Every entry then carries its own answer. pop discards a value and its minimum together, and the entry underneath already holds the correct minimum for the new state. Nothing needs recomputing, ever.
Real-world analogy
A ledger where each row records both the transaction and the running balance after it. Undoing the last transaction does not require recalculating anything — the previous row already shows the correct balance.
Watch it run
Approach
Store pairs, not bare values
Each stack entry is (value, min_so_far).
On push
new_min = min(value, current_min) where current_min is the top entry's minimum, or the value itself if the stack is empty. Push (value, new_min).
On pop
Remove the top entry. The minimum for the remaining stack is already stored in the new top.
top returns the value part; getMin returns the minimum part
Both are single array reads.
Solution
class MinStack:
"""A stack where every operation, including getMin, is O(1)."""
def __init__(self) -> None:
# Each entry is (value, minimum of the stack at push time).
self._stack: list[tuple[int, int]] = []
def push(self, val: int) -> None:
current_min = self._stack[-1][1] if self._stack else val
self._stack.append((val, min(val, current_min)))
def pop(self) -> None:
self._stack.pop()
def top(self) -> int:
return self._stack[-1][0]
def getMin(self) -> int:
return self._stack[-1][1]The two-stack variant
The same idea split across two stacks — one for values, one for minimums. Behaviourally identical, and some find it easier to reason about:
class MinStackTwoStacks:
def __init__(self) -> None:
self._values: list[int] = []
self._mins: list[int] = [] # _mins[i] = min of _values[0..i]
def push(self, val: int) -> None:
self._values.append(val)
self._mins.append(min(val, self._mins[-1]) if self._mins else val)
def pop(self) -> None:
self._values.pop()
self._mins.pop() # must stay the same height as _values
def top(self) -> int:
return self._values[-1]
def getMin(self) -> int:
return self._mins[-1]A tempting optimisation that goes wrong
A common refinement is to push onto the min-stack only when the new value is strictly smaller, saving memory. It works — but only if pop also pops the min-stack only when the popped value equals the current minimum.
With push(0), push(0), the strict version stores one minimum. The first pop removes it, and getMin now reports the wrong answer for a stack that still contains a 0. The fix is to push on <= rather than <. Storing a minimum for every entry, as above, sidesteps the whole hazard for a constant factor of memory.
Complexity Analysis
Time Complexity
O(1)
Space Complexity
O(n)
- Time — every operation is a single array push, pop or index read. No loops anywhere.
- Space —
O(n)for the values plusO(n)for the minimums. Doubling memory to turn anO(n)query intoO(1)is a deliberate trade, and the point of the exercise.
Edge Cases
Related Problems
- Valid Parentheses — the plain stack, without extra state
- Insert Delete GetRandom O(1) — another design problem where auxiliary structures buy
O(1)operations - Trapping Rain Water — carrying a running extreme alongside a traversal