Min Stack
Keep a parallel stack of the minimum-so-far.
Both Stacks, Call by Call
Problem
Design a stack data structure that supports adding an integer, removing the top integer, reading the top integer, and retrieving the smallest integer currently stored. Every operation, including retrieving the minimum, should run in O(1) time.
Examples
Input: push(-2), push(0), push(-3), getMin(), pop(), getMin(), top(), pop(), getMin()
Output: [null, null, null, -3, null, -2, 0, null, -2]
Input: push(5), push(2), push(4), getMin(), pop(), getMin()
Output: [null, null, null, 2, null, 2]
The Goal
Build a stack with push, pop, top and getMin, where every call takes O(1) time.
top is easy: it's the last value pushed. The minimum is the hard part. It can be buried anywhere, and scanning for it makes getMin cost O(n).
So work the minimum out as you go. On each push, store what the minimum is at that height.
No scans
getMin has to answer without looking at older entries.
Work out the minimum when you push, and read it back later.
Key Idea: A Second Stack of Minimums
Keep a second stack, mins, beside the stack. Entry k of mins is the smallest value at or below height k.
A push adds min(val, mins[-1]) to mins: the new minimum is either the new value or the one under it. A pop takes one entry off each stack, and the minimum from before that push is back on top.
getMin reads mins[-1].
Each value on the stack has one entry in mins beside it.
The Algorithm
class MinStack:
def __init__(self):
self.stack = []
self.mins = []
def push(self, val):
self.stack.append(val)
self.mins.append(min(val, self.mins[-1]) if self.mins else val)
def pop(self):
self.stack.pop()
self.mins.pop()
def top(self):
return self.stack[-1]
def getMin(self):
return self.mins[-1]Every method touches only the tops of the two stacks.
| Design | getMin | Extra space | How |
|---|---|---|---|
| Stack of minimums | O(1) | O(n) | Reads the top of mins |
| Scan the stack | O(n) | O(1) | Looks at every value |
| One minimum variable | O(1), but pop can cost O(n) | O(1) | Rescans when the minimum is popped |
Walkthrough
Run push(-2), push(0), push(-3), getMin(), pop(), getMin(), top(), pop(), getMin().
After the three pushes, the stack is [-2, 0, -3] and mins is [-2, -2, -3], so getMin returns -3. The pop takes -3 off both, and getMin returns -2 with no scan. top returns 0. After the second pop, getMin still returns -2.
The calls return [None, None, None, -3, None, -2, 0, None, -2].
Checkpoint · predict the next step
Step 2 of 15 on the stage: push(-2): put -2 on the stack.
call on "push -2" (index 0) · stack = [-2] · mins = [] · returns = []
Pitfalls
- Add to
minson every push. Adding only when a value beats the minimum loses it: afterpush(2), push(2), pop(),minsis empty. - Pop from both stacks, so they stay the same height.
- Don't mix up
topandgetMin. With[-2, 0]on the stack,topis 0 and the minimum is -2. pop,topandgetMinonly come while something is on the stack, as on the stage.
Why not scan the stack inside getMin?
Complexity
Each call does a fixed amount of work at the tops of the stacks, so every call is O(1).
mins holds one entry per value on the stack, so extra space is O(n). That's the trade: memory for a minimum you never have to search for.
Every call O(1), paid for with a second stack
- pushOne comparison, then a push onto each stack.dominantO(1)
- popOne pop from each stack.dominantO(1)
- topReads the top of the stack.dominantO(1)
- getMinReads the top of mins.dominantO(1)
- minsOne entry per value.O(n)
| n | 10 | 100 | 1,000 | 10,000 |
|---|---|---|---|---|
| O(1) | 1 | 1 | 1 | 1 |
| O(n) | 10 | 100 | 1K | 10K |
O(1) per call, with O(n) extra space for mins.
In short
Alongside the main stack, push the current minimum at each step (the smaller of the new value and the previous min). Pop both together. getMin is then the top of the min-stack in O(1), with no scanning.
Common mistake
Scanning the whole stack for the min on each getMin call — that's O(n) and defeats the purpose.