Min Stack — Step-by-Step Visualization

Algorithm Pattern

Dual Stack Tracking

Key Idea

To achieve O(1) for `getMin()`, we maintain a second stack (the 'min stack') alongside the main data stack. Each entry in the min stack stores the minimum value observed in the main stack up to that level. When pushing a new value `v`, the new top of the min stack is `min(v, minStack.top())`. When popping, we pop from both.

Step-by-Step Approach

1. Initialize `stack = []` and `minStack = []`.
2. Push(val): `stack.push(val)`. `minStack.push(min(val, minStack[-1] or val))`.
3. Pop(): `stack.pop()`, `minStack.pop()`.
4. Top(): Return `stack[-1]`.
5. GetMin(): Return `minStack[-1]`.

Common Gotchas

• All operations must be O(1).
• The min stack must always have the same size as the main stack (or use an optimization where we only push if smaller, but keeping them same-size is easier to visualize).