Min Stack
MediumO(1) minimum alongside push/pop
Keep a second pile that always has the smallest value on top, so you can peek at the minimum instantly.
The idea
Keep a second stack that mirrors the main one but stores the running minimum. The current minimum is always its top, so getMin is 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.