How do you design a stack that returns the minimum element in O(1)?
SHORT ANSWER
Keep a second stack of minimums. On each push, also push the smaller of the new value and the current minimum. Pop from both together, and the top of the second stack is always the minimum.
Explain it simply
Scanning the whole stack to find the smallest value would be O(n). Instead, remember the minimum at every height of the stack, like a note stuck beside each plate saying "the lightest plate from here down is X".
When you pop a plate, throw away its note too. The note on the new top is always correct.
Example
js
class MinStack {
constructor() {
this.stack = [];
this.mins = [];
}
push(x) {
this.stack.push(x);
const currentMin = this.mins.length ? this.mins[this.mins.length - 1] : x;
this.mins.push(Math.min(x, currentMin));
}
pop() {
this.mins.pop();
return this.stack.pop();
}
getMin() {
return this.mins[this.mins.length - 1];
}
}
const s = new MinStack();
s.push(5);
s.push(3);
s.push(7);
console.log(s.getMin()); // Output: 3
s.pop();
s.pop();
console.log(s.getMin()); // Output: 5Complexity
push, pop, getMin all O(1) time; extra space O(n).
What to say in the interview
"I keep a parallel stack where each entry stores the minimum of everything below and including that position. Push, pop and getMin are all O(1) time, with O(n) extra space for the second stack."
Common mistakes
- Storing just one minimum variable, which becomes wrong after the minimum is popped.
- Forgetting to pop from the minimum stack together with the main stack.