Min Stack
Min Stack is LeetCode 155 (Medium). Design a stack that supports getMin alongside the usual operations:
push(val)putsvalon top.pop()removes the top element.top()returns the top element without removing it.getMin()returns the smallest element currently in the stack.
Every operation must run in O(1) time. pop, top and getMin are only called on a non-empty stack. Values span the full 32-bit range, and there are up to 3 × 10⁴ calls, so a scan inside getMin is too slow.
- -2³¹ <= val <= 2³¹ - 1
- Methods pop, top and getMin operations will always be called on non-empty stacks.
- At most 3 * 10⁴ calls will be made to push, pop, top, and getMin.
Intuition
A normal stack already gives O(1) push, pop and top. The hard part of min stack is how to get minimum element from stack in O(1) after a pop: if the minimum is removed, what is the new one? Scanning is O(n), and a single min variable forgets the old minimum.
The key observation is that a stack only changes at its top. While a value sits in the stack, everything below it stays exactly the same, so the minimum of that value and everything beneath it is fixed the moment it is pushed. Store that minimum alongside the value, and every older minimum is still there when the top is popped.
When a data structure must answer a summary query (min, max, sum) in O(1) and only changes at one end, cache the summary per entry at the moment it is added. The same trick gives a max stack, and two such stacks build a queue with O(1) amortised getMin (the sliding-window minimum idea).
Approach
Before reading on, push 5, 3, 7, 3, then pop twice, and write what getMin must return after each step. Decide what extra information a pop needs to get this right.
Two ways to solve it
Push each value together with the minimum of itself and everything below it, so the top pair always knows the current minimum.
- Simplicity: one stack, one comparison per push.
- Duplicates: equal minimums need no special rule.
- Memory: one extra int for every element.
The easiest version to get right first time.
Keep a plain value stack, and push onto a second min stack only when val <= its top. Pop it when the popped value equals its top.
- Memory: often less, as the min stack grows only on a new or equal minimum.
- Worst case: descending pushes fill both stacks equally.
- Trap:
<instead of<=breaks on duplicate minimums.
Worth it when memory is tight.
Both run every operation in O(1), and two stacks can use less memory; pairs win on simplicity, with one stack and no duplicate-minimum rule to get wrong. The steps, code and live demo below follow the pairs, and the two-stack code is further down.
Store pairs
Each stack entry is (value, min so far), where min so far is the smallest value in this entry and everything beneath it. In the min stack Python code each entry is a tuple; C++ uses pair<int, int> and Java an int[2].
push(val)
- Empty stack – the minimum is
valitself. - Otherwise – the minimum is
min(val, top's min).
Push (val, that minimum). Comparing with the top's stored minimum is enough, because that one number already summarises every element below it.
pop(), top(), getMin()
pop()– remove the top pair. Its minimum leaves with it, and the pair below still holds the correct older minimum.top()– return the value half of the top pair.getMin()– return the min half of the top pair.
Why every operation is O(1)
Each method reads or writes only the top entry, with one comparison at most. No loop depends on the stack size, so all four operations are constant time. Space is O(n): two numbers per element.
Min Stack solution in Python | C++ | Java
getMin is just a look at the top pair.min variable could not recover that.getMin is just a look at the top pair.getMin is just a look at the top pair.min variable could not recover that.min variable could not recover that.Two-stack min stack
values is an ordinary stack. mins holds only the values that were a new or equal minimum when pushed, so its top is always the current minimum, and it is popped only when that value leaves values.
Common pitfalls
Keeping one min variable
def push(self, val):
self.stack.append(val)
self.low = min(self.low, val)def push(self, val):
low = min(val, self.stack[-1][1]) if self.stack else val
self.stack.append((val, low))After popping the current minimum there is no way to know the previous one without scanning. Push 3, 1, pop: a single variable still says 1.
Two stacks that skip equal minimums
if val < self.mins[-1]:
self.mins.append(val)if val <= self.mins[-1]:
self.mins.append(val)In the two-stack version the min stack must also take duplicates. Push 0, 1, 0 then pop: with < the second 0 never reached the min stack, so popping it also pops the first 0's entry, and the min stack is empty while a 0 is still in the stack.
Scanning for the minimum in getMin
def getMin(self):
return min(self.stack)def getMin(self):
return self.stack[-1][1]min(self.stack) is O(n), which fails the O(1) requirement and times out on 3×10⁴ calls.
Edge cases
Pairs store values as they are, with no arithmetic, so nothing can overflow. The encoded one-stack variant computes 2·val − min, which overflows a 32-bit int here.
Complexity
Three ways to build a min stack
All three give O(1) operations. They differ in how much extra memory they use and how easy they are to get right.
| Design | Extra space | Watch out for |
|---|---|---|
Stack of (value, min) pairs (this page) | one int per element | nothing: simplest to prove correct |
| Value stack + min stack | only when the minimum changes or repeats | push to the min stack on <=, not < |
One stack, encoded values (2·val − min) | one variable | overflow on large values; hard to explain |
Min Stack FAQ
Can a min stack use only O(1) extra space?
Yes, by keeping a single min variable and pushing an encoded value 2·val − min whenever val is a new minimum; on pop, a top below min signals the old minimum is 2·min − top. It saves memory but needs 64-bit arithmetic to avoid overflow, and it is much harder to explain in an interview. The pairs-based min stack solution on this page is the safer choice.