Min Stack
Understanding the Problem
We need a stack that supports the usual push, pop, and top operations and also returns the minimum element at any time, with every operation running in O(1). The standard stack operations are easy. The hard part is getMin.
With a plain stack, finding the minimum means scanning every element, which is O(n). The question is how to track the minimum as elements come and go, without ever scanning.
The minimum can only change in two situations: when we push an element smaller than the current minimum, or when we pop an element that was the current minimum. So we need a way to recover what the minimum was before the popped element arrived.
Key Constraints:
-2^31 <= val <= 2^31 - 1→ Values span the full 32-bit signed integer range, including the minimum value -2147483648. A sentinel value chosen to mean "empty" could collide with a real input, so avoid that design.- At most
3 * 10^4calls → The problem requires O(1) per operation regardless of call volume, so we need a design that tracks the minimum incrementally rather than recomputing it. - Operations on non-empty stacks → pop, top, and getMin are never called on an empty stack, so we do not need to handle that case.
Approach 1: Brute Force (Linear Scan for Min)
Intuition
Use a regular stack for push, pop, and top, then scan the entire stack whenever getMin is called. This ignores the O(1) requirement for getMin, but it establishes a correct baseline.
Push, pop, and top are already O(1) with a standard stack. Only getMin is expensive: each call iterates through all elements currently in the stack to find the smallest one.
Algorithm
- Maintain a standard stack (or list) to store elements.
- For push, add the element to the top of the stack.
- For pop, remove the top element.
- For top, return the top element without removing it.
- For getMin, iterate through all elements in the stack and return the smallest one.
Example Walkthrough
Code
- Time Complexity: O(1) for push, pop, and top. O(n) for getMin, where n is the number of elements in the stack, since we scan every element.
- Space Complexity: O(n) for storing the n elements in the stack.
The brute force is correct but getMin scans the entire stack on every call. The next approach tracks the minimum as elements are pushed and popped, so getMin never scans.
Approach 2: Two Stacks
Intuition
The minimum of a stack depends only on the elements currently in it, and because we only add and remove from the top, those elements are always a prefix of the push history. If we record what the minimum was at each level of the stack, popping an element restores the previous minimum.
One way to do this is with a second stack, the min stack. Every time we push a value, we also push the current minimum onto the min stack. When we pop, we pop from both. The top of the min stack always holds the current minimum.
The min stack maintains one invariant: at any stack height h, the value at height h in the min stack is the minimum of all elements from the bottom up to height h. When we pop an element, the height drops by one, and the new top of the min stack already holds the correct minimum for that reduced height, computed back when that level was pushed.
This is a prefix minimum over the push history. Because stack operations only affect the top, each level's minimum never depends on elements pushed later, so the invariant holds through any sequence of pushes and pops.
Algorithm
- Initialize two stacks: one for values (
stack) and one for tracking minimums (minStack). - For push(val): push val onto stack. If minStack is empty or val is less than or equal to the current minimum, push val onto minStack. Otherwise, push the current minimum again (so minStack stays in sync).
- For pop(): pop from both stack and minStack.
- For top(): return the top of stack.
- For getMin(): return the top of minStack.
Example Walkthrough
Code
- Time Complexity: O(1) for all four operations. Push, pop, top, and getMin each do a constant number of stack operations.
- Space Complexity: O(n), where n is the number of elements in the stack. We maintain two stacks of the same size.
The two-stack approach gives O(1) for every operation but maintains two separate data structures kept in sync. The next approach folds them into a single stack that stores pairs.
Approach 3: Single Stack with Pairs
Intuition
Instead of maintaining two separate stacks, store pairs of (value, currentMin) in a single stack. Each entry carries its own minimum snapshot. This produces the same answers as the two-stack approach with one data structure, which removes the need to keep two stacks in sync.
Algorithm
- Initialize a single stack that stores pairs (value, currentMinimum).
- For push(val): compute the new minimum as the smaller of val and the current stack's minimum (or val if the stack is empty). Push the pair (val, newMin).
- For pop(): pop the top pair.
- For top(): return the first element of the top pair.
- For getMin(): return the second element of the top pair.
Example Walkthrough
Code
- Time Complexity: O(1) for all four operations. Each operation does exactly one push, pop, or peek.
- Space Complexity: O(n), where n is the number of elements in the stack. Each element stores a pair, so the constant factor is 2x per element, but asymptotically it is still O(n).