The problem
Design a stack supporting push, pop, top, and getMin — all in O(1).
Stuck? Reveal hints one at a time
How to approach it
- 1Each stack entry holds (value, minAtThisPoint).
- 2push(x): minAtThisPoint = min(x, current top’s min) — or x if empty.
- 3pop/top operate on the value part; getMin reads the top’s min part.
Key insight
The min history is immutable per position — snapshotting it per entry costs O(1) each and makes deletion-proof minimum tracking trivial.
The solution
Watch out for
- A second "min stack" that only pushes new minima saves memory but must pop conditionally — the paired version is harder to get wrong.
- For a MAX stack, flip the comparison; the structure is identical.