Min Stack
The key idea
Keep a second stack that always holds the minimum of everything below the current top. Each push records the smaller of the new value and the previous minimum, so
getMin is just reading the top of that stack — O(1), no scanning.Problem
Design a stack that supports push, pop, top, and retrieving the minimum element — all in constant time.
Implement the MinStack class:
- MinStack() initializes the stack object.
- push(val) pushes the element val onto the stack.
- pop() removes the element on the top of the stack.
- top() gets the top element of the stack.
- getMin() retrieves the minimum element in the stack.
You must implement a solution with O(1) time complexity for each function.
Constraints
-2^31 <= val <= 2^31 - 1pop,top, andgetMinoperations are always called on non-empty stacks.- At most
3 * 10^4calls will be made topush,pop,top, andgetMin.
Examples
Input: ["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output: [null,null,null,null,-3,null,0,-2]
Complexity
Time: O(1) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization