Min Stack easy
Description
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Implement the MinStack class:
push(val)— pushvalonto the stackpop()— remove the top elementtop()— get the top elementgetMin()— get the minimum element currently in the stack, in O(1)
Examples
MinStack stack
stack.push(-2)
stack.push(0)
stack.push(-3)
stack.getMin() # -> -3
stack.pop()
stack.top() # -> 0
stack.getMin() # -> -2Constraints
- Methods
push,pop,top, andgetMinmust all run in O(1) time. pop,top,getMinare always called on non-empty stacks.
Intuition
The first idea: scan the stack to find the min on every getMin call. That’s O(n) — too slow.
The trick: keep a second stack that tracks the minimum at each level. When we push val, we also push min(val, currentMin) onto the min-stack. When we pop, we pop from both. Then getMin is just peek of the min-stack — O(1).
Main stack: [-2, 0, -3]
Min stack: [-2, -2, -3] ← min seen so far at each depthWhen we pop -3, both stacks pop together; the min stack’s top becomes -2, which is the correct min of what’s left.
Code
Explanation
- Each entry in
minsanswers: “what’s the smallest element in the stack from the bottom up to this depth?” - Pushing a new value either makes the new min (
val) or inherits the previous min (mins.top()). - Because both stacks grow and shrink in lockstep,
mins.top()always reflects the min of the current stack contents.
A common optimization stores mins only when a new minimum appears — saving space when values tend to increase. But you have to be careful in pop: only pop from mins if the popped value equals mins.top(). The straightforward “push every time” version above is easier to get right under interview pressure.
Analysis
- Time:
O(1)for all four operations. - Space:
O(n)— two stacks, each up to sizen.