Min Stack
Problem
Design a stack that supports push, pop, top, and getMin, where getMin returns the smallest element currently in the stack. Every operation must run in constant time.
Examples
Constraints
- • -2^31 <= val <= 2^31 - 1
- • pop, top and getMin are called on a non-empty stack
- • Up to 3 * 10^4 calls
Hints & approach
Hint 1
Keeping one "current minimum" variable breaks when you pop that minimum.
Hint 2
What was the minimum at the moment each element was pushed?
Hint 3
Store that alongside each element, or keep a second stack of minimums.
Approachtry the hints first
Push pairs (value, minSoFar) where minSoFar is the smaller of the value and the previous top's minSoFar. top returns the first field, getMin the second, and pop removes the pair. Because each entry remembers the minimum of everything beneath it, popping automatically restores the earlier minimum. A second stack that only pushes when a new value is <= its top saves some memory.
Time O(1) per operation · Space O(n)