Part 2 · Problems · Stack
Min Stack
#155 · Medium · LeetCode
Design a stack with push, pop, top and getMin, all O(1).
push -2, push 0, push -3, getMin -> -3, pop, top -> 0, getMin -> -2
Ask before coding
- pop and top only called on a non-empty stack?
Hint
Store the min at each height, not just one global min.
Approach
A second stack where mins[i] is the minimum of everything up to i. Push and pop both stacks together.
Time O(1) each Space O(n)
Watch it run
Solution (JavaScript, tested)
class MinStack {
items = [];
mins = []; // mins[i] = min of items[0..i]
push(x) {
this.items.push(x);
this.mins.push(this.mins.length ? Math.min(x, this.mins[this.mins.length - 1]) : x);
}
pop() {
this.items.pop();
this.mins.pop();
}
top() {
return this.items[this.items.length - 1];
}
getMin() {
return this.mins[this.mins.length - 1];
}
}Traps
- A single min variable breaks after popping the min.
Say out loud: The trick is remembering the min at every level, so popping restores the old min for free.