visual walkthrough
Min Stack
Keeping auxiliary state per element is a reusable design trick.
The idea
The minimum of a stack changes only when you push a smaller value or pop the current minimum. So store, next to every element, the minimum of everything beneath and including it.
Then getMin is just a peek at the matching top entry, and popping automatically restores the previous minimum.
Complexity
| approach | time | space |
|---|---|---|
| One stack, scan for min | O(n) getMin | O(n) |
| Parallel min stack | O(1) all | O(n) |