Stack · LC #155
Min Stack
Design a stack that retrieves the minimum element in O(1) time by storing a (value, currentMin) pair at each level.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Design a stack that supports `push`, `pop`, `top`, and `getMin` operations - all in O(1) time. Implement the MinStack class: - `MinStack()` initializes the stack. - `void push(int val)` pushes val onto the stack. - `void pop()` removes the top element. - `int top()` returns the top element. - `int getMin()` returns the minimum element in the stack.
Sample I/O
MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); // returns -3 minStack.pop(); minStack.top(); // returns 0 minStack.getMin(); // returns -2
Intuition
How to Think About It
Intuition
The challenge is that popping an element might remove the current minimum - so we need a way to restore the previous minimum. The insight: store the minimum snapshot at the time of each push so that when we pop, the new top automatically has the correct minimum for that state.
Core Concept
Each stack entry is a pair `(value, minSoFar)` where `minSoFar` is the minimum of all values currently in the stack including this one. On push, compute `min(newValue, top.minSoFar)`. On pop, the pair is discarded. `getMin()` reads `top.minSoFar` in O(1). The invariant is: every entry stores the minimum of the sub-stack from bottom up to that entry.
When to use
Any problem requiring O(1) access to a running minimum/maximum of a dynamic collection that supports push/pop. Stock span, sliding window maximum (combined with deque), undo-min tracking.
When NOT to use
When you need rank-based statistics (kth smallest) - use an order-statistic tree or sorted structure. When memory per entry is constrained and duplicating the min is too costly (use a separate auxiliary min stack instead).
Key Insights
What to Know Cold
- Alternative: maintain a separate auxiliary min-stack that only pushes when a new minimum is seen (slightly more space-efficient on average).
- The pair approach is simpler and has the same worst-case space; the auxiliary stack only wins when there are few distinct minimums.
- On pop, the minimum is automatically "restored" because the new top carries its own `minSoFar` from the time it was pushed.
- Duplicate minimum values are handled correctly by storing the min per entry - no need for reference counting.
- The `minSoFar` value at any entry is monotonically non-increasing from bottom to top (each push can only keep or lower the min).
1 example
Worked Examples
Pop restores prior minimum automatically
Push -2, 0, -3 → getMin=-3. Pop. getMin should now be -2.
Each entry carries its own snapshot. After pop(-3), the top is (0, -2) - minSoFar=-2 was stored when 0 was pushed. No extra work needed.
const s = new MinStack(); s.push(-2); // stack: [(-2,-2)] s.push(0); // stack: [(-2,-2),(0,-2)] s.push(-3); // stack: [(-2,-2),(0,-2),(-3,-3)] s.getMin(); // -3 s.pop(); // stack: [(-2,-2),(0,-2)] s.top(); // 0 s.getMin(); // -2 ← restored from stored pair
Output: getMin()=-3, top()=0, getMin()=-2
Demonstrates the invariant: each pop automatically restores the correct minimum without any scanning or extra bookkeeping.