Implement Min Stack
HardStore the minimum alongside each element
Problem
Design a stack that also returns its minimum element in O(1) time.
Store the minimum-so-far with each element (or in a second stack) so getMin is instant.
The idea
Push the running minimum with every value, so the top always carries both the element and the smallest value below it. Popping restores the previous minimum automatically, making getMin a constant-time read.
The trick
- Push min(value, currentMin) with each element.
- An encoding trick can do it in O(1) extra space, but the pair is clearer.
- All four operations are O(1).
Step 1 of 8. A second stack mirrors the running minimum, so getMin is O(1).
1/8
Optimal
timeO(1)spaceO(n)
Track the min per level.
1push(x){ this.s.push(x);2 this.mins.push(Math.min(x, this.min())); }3pop(){ this.mins.pop(); return this.s.pop(); }4getMin(){ return this.mins.at(-1); }Memory
- min
- —
Output
- getMin
- —
- min
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- push 3, push 5, getMin
- Output:
- 3
- Explanation:
- Track the running minimum alongside each push.
Example 2
- Input:
- push 5, push 2, push 1, getMin
- Output:
- 1
- Explanation:
- getMin returns the smallest so far.
Example 3
- Input:
- push 2, pop, getMin
- Output:
- (empty)
- Explanation:
- After popping the only element, the stack is empty.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.