Min Stack
Design a stack that supports retrieving the minimum element in constant time.
MediumSolve on LeetCode
Problem Understanding
Design a stack that supports push, pop, top, and getMin operations, all in O(1) time.
push(val): Pushes element val onto stack.pop(): Removes element on top of stack.top(): Gets the top element.getMin(): Retrieves minimum element in the stack.
Algorithm Strategy
A standard stack gives O(1) push/pop, but finding the minimum usually takes O(N). To get O(1) min, we trade Space for Time.
Strategy:
Maintain a second stack, minStack. Whenever we push a value x onto the mainStack, we also push min(x, minStack.top()) onto the minStack. The top of minStack always represents the minimum of the mainStack at that height.
Interactive Visualization
Visualize two stacks growing in parallel. The MinStack tracks the minimum value seen 'so far'.
Dry Run
Ops: push 2, push 0, push 3, getMin, pop, top, getMin
| Op | stack | minStack | Returns |
|---|---|---|---|
| push 2 | [2] |
[2] |
- |
| push 0 | [2, 0] |
[2, 0] |
- |
| push 3 | [2, 0, 3] |
[2, 0, 0] (min(3, 0) = 0) |
- |
| getMin | [2, 0, 3] |
[2, 0, 0] |
0 |
| pop | [2, 0] |
[2, 0] |
- |
| top | [2, 0] |
[2, 0] |
0 |
| getMin | [2, 0] |
[2, 0] |
0 |
Edge Cases & Common Mistakes
- Empty Stack:
getMinon empty stack (usually invalid op by problem statement, but good to check). - Duplicate Min: If we push
0then another0, minStack should store both so when one pops, the other remains.
Solution
Using two stacks.
Min Stack Code
1var MinStack = function() {2 this.stack = [];3 this.minStack = [];4};56MinStack.prototype.push = function(val) {7 this.stack.push(val);8 this.minStack.push(this.minStack.length === 0 ? val : Math.min(val, this.minStack[this.minStack.length - 1]));9};1011MinStack.prototype.pop = function() {12 this.stack.pop();13 this.minStack.pop();14};1516MinStack.prototype.top = function() {17 return this.stack[this.stack.length - 1];18};1920MinStack.prototype.getMin = function() {21 return this.minStack[this.minStack.length - 1];22};