Min Stack
A medium Stack interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Stack
- Sheets
- 3
- Core for
- 9 roles
The problem
Build a stack with four operations: push a value, pop the top, read the top, and report the smallest value the stack currently holds. Every one of these must take O(1) time, including the minimum lookup after pops.
Example 1
- Input
- Operations: push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()
- Output
- -3, 0, -2
- Why
- After pushing -2, 0, and -3, the minimum is -3. After popping -3, the top becomes 0 and the minimum returns to -2.
Example 2
- Input
- Operations: push(0), getMin(), push(1), getMin(), pop(), top(), getMin()
- Output
- 0, 0, 1, 0
- Why
- Pushing 0 makes the minimum 0. Pushing 1 keeps the minimum at 0. After popping 1, the top is back to 0.
Constraints
- -2^31 <= val <= 2^31 - 1
- At most 3 * 10^4 calls will be made to push, pop, top, and getMin
- There is at least one element in the stack when pop, top, or getMin is called
How to think about it
Updated 2026-09-29A regular stack already remembers chronological history, but a minimum needs to track history along the lower envelope. When an element is pushed, the running minimum is fixed for as long as that element stays alive. Coupling each value with the minimum at that exact depth means popping an item automatically restores whatever minimum existed before it.
Approaches, worst first
Linear search on getMin
time O(n) · space O(1)
Store elements in a standard stack. Push, pop, and top take constant time, but getMin scans the entire backing store from bottom to top to identify the smallest value. It does zero extra bookkeeping on push, but loses immediately when queries are frequent.
Paired value and running minimum
time O(1) · space O(n)
Push a pair `(val, minSoFar)` onto the stack, where `minSoFar` is `min(val, currentMin)`. Every operation reads or mutates the head of the stack in O(1) time. It doubles storage compared to an unadorned array, but completely avoids auxiliary lookups.
Two parallel stacks with duplicate suppressionWrite this one
time O(1) · space O(n)
Maintain a data stack and a distinct min-stack. Only push to the min-stack when `val <= minStack.top()`, and only pop from it when the popped value equals the min-stack top. Achieves worst-case O(1) across all operations while drastically reducing memory when elements arrive out of order.
Where people lose marks · 3
- Popping the main stack without checking if its value matches the min-stack top leaves stale minimums stranded on the auxiliary stack.
- Using `<` instead of `<=` when pushing to the min-stack drops duplicate minimums. Popping the first instance then evicts the minimum prematurely even though identical copies remain.
- Integer difference encoding (`2 * val - min`) risks signed 32-bit integer overflow when values approach -2^31 or 2^31 - 1 without 64-bit storage.
The theory behind it
Stack — the ground this problem stands on. All Stack problems
What Stack is
A stack is a vertical pile of cafeteria trays where items enter and depart from one single opening at the top. The most recent item set down is the first one retrieved, while items deposited earlier remain buried underneath until newer arrivals are lifted away. This strict last-in, first-out sequence guarantees that older context stays preserved until all newer nested actions run to completion.
When to reach for it
Reach for a stack whenever an algorithm encounters nested structures like matched brackets, tags, or algebraic formulas. Problems demanding undo operations, function execution histories, or evaluating postfix arithmetic require this discipline. It is also the primary structure for monotonic queries where a task asks for the nearest greater or smaller value adjacent to each position in a series.
How the pattern works
Picture peeling layers back in exact reverse order of their arrival. Push items as pending jobs or unclosed delimiters encounter the scan. When closing boundaries appear, pop the topmost entry and check for compatibility. For monotonic patterns, maintain an invariant where elements on the stack remain strictly increasing or decreasing; pop any items that violate this rule before recording candidate answers and pushing the current item.
More Stack problems
Target Roles
Core requirement for 9 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .