Min Stack
Last Updated: March 29, 2026
Understanding the Problem
We need to build a stack, but with a twist: on top of the usual push, pop, and top operations, we also need to retrieve the minimum element at any time, and all of these must run in O(1). The regular stack operations are straightforward. The real challenge is getMin.
If we just had a regular stack, finding the minimum would require scanning every element, which is O(n). The question becomes: how do we keep track of the minimum as elements come and go, without ever needing to scan?
The key observation is that the minimum can only change in two situations: when we push a new element that is smaller than the current minimum, or when we pop an element that was the current minimum. So we need a way to "remember" what the minimum was before that element arrived.
Key Constraints:
-2^31 <= val <= 2^31 - 1→ Values span the full 32-bit integer range, including Integer.MIN_VALUE. Be careful if using sentinel values.- At most
3 * 10^4calls → Performance is not a concern at this scale, but the problem explicitly requires O(1) per operation, so we need a design-level solution, not brute force. - Operations on non-empty stacks → We don't need to handle edge cases for pop/top/getMin on an empty stack.
Approach 1: Brute Force (Linear Scan for Min)
Intuition
The simplest approach is to use a regular stack for push, pop, and top, and then scan the entire stack whenever getMin is called. This ignores the O(1) requirement but helps us understand the baseline.
Every time someone asks for the minimum, we iterate through all elements currently in the stack and find the smallest one. Push, pop, and top are already O(1) with a standard stack. Only getMin is expensive.
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 works but getMin scans the entire stack every time. What if we tracked the minimum as we go, so we never need to scan at all?
Approach 2: Two Stacks
Intuition
Here is the core insight: the minimum of a stack depends only on the elements currently in it, and those elements are always a prefix of our push history (since we only add and remove from the top). So if we record what the minimum was at each "level" of the stack, popping an element automatically reveals the previous minimum.
The cleanest way to do this is with a second stack, often called 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 works because of a simple invariant: at any stack height h, minStack[h] holds the minimum of all elements from the bottom of the stack up to height h. When we pop an element, we reduce the height by one, and the new top of the min stack already has the correct minimum for that reduced height. We precomputed it when we pushed.
This is essentially a prefix minimum over the push history. Since stack operations only affect the top, each prefix minimum is independent of future operations. That is why this approach is both correct and O(1).
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 us O(1) for everything, but we maintain two separate data structures. What if we combined them into a single stack that stores pairs?
Approach 3: Single Stack with Pairs
Intuition
Instead of maintaining two separate stacks, we can store pairs of (value, currentMin) in a single stack. Each entry carries its own minimum snapshot. This is functionally identical to the two-stack approach but uses a single data structure, which some find cleaner.
Same principle as the two-stack approach. Each entry in the stack carries a snapshot of the minimum at the time it was pushed. Popping reveals the previous entry, which has its own correct snapshot. The invariant is maintained without any extra coordination, because each pair is self-contained.
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).