#155
Min Stack
Medium Stack of (value, min) pairs
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Design a stack that supports push, pop, top and getMin, all in O(1).
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: a stack with getMin in O(1).
Why this works: store with every value the minimum at that moment; popping restores the old minimum automatically.
Example: push -2, 0, -3
[(-2,-2), (0,-2), (-3,-3)] → min -3pop → min -2
✦Hints open one at a time
The minimum changes only when you push or pop.
Store, with each element, the minimum of the stack at that moment.
↗Approach
Push pairs [value, min(value, current min)]. getMin reads the top pair's second field. Popping restores the previous minimum automatically.
</>Solution (Java)
import java.util.*;
class MinStack {
private final Deque<int[]> stack = new ArrayDeque<>(); // {value, min so far}
public void push(int val) {
int min = stack.isEmpty() ? val : Math.min(val, stack.peek()[1]);
stack.push(new int[]{val, min});
}
public void pop() {
stack.pop();
}
public int top() {
return stack.peek()[0];
}
public int getMin() {
return stack.peek()[1];
}
}!Common mistake
Keeping a single min variable — after popping the minimum you don't know the next one.
Complexity
- Time: O(1) per operation.
- Space: O(n).
Topic: Stack & Queue
🎬 Episodes 46–52: video coming soon