Min Stack
Problem
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
- Methods push, pop, top, and getMin must all operate in O(1) time.
- pop, top, and getMin will always be called on non-empty stacks.
Example
push(2), push(0), push(3), push(0), getMin(), pop(), getMin(), pop(), getMin(), pop(), getMin()[null, null, null, null, 0, null, 0, null, 0, null, 2]The stack evolves as follows: push 2 → stack=[2], min_stack=[2]; push 0 → stack=[2,0], min_stack=[2,0]; push 3 → stack=[2,0,3], min_stack=[2,0,0]; push 0 → stack=[2,0,3,0], min_stack=[2,0,0,0]. getMin() returns 0 (the top of min_stack). pop() removes 0 → stack=[2,0,3], min_stack=[2,0,0]. getMin() still returns 0. Subsequent pops and getMin() calls update the stacks accordingly, always returning the current minimum in O(1) time.
Approach
Straightforward Solution
A naive approach is to scan the entire stack to find the minimum after each push or pop, resulting in O(n) time per getMin call, which is inefficient for large stacks.
Core Observation
A stack supports last-in-first-out operations, but retrieving the minimum element in constant time requires additional state tracking. The minimum element can change with each push or pop, so a secondary structure must track the minimums efficiently.
Path to Optimal
PreviewThe key insight is to maintain a parallel stack (min_stack) that tracks the minimum element at each level of the main stack. When pushing a new value, compare it with the current minimum and push the smaller one onto min_stack…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewUse two stacks: one for all values (stack) and one for the current minimums (min_stack). On push, append the value to stack and the minimum of the new value and the current min to min_stack…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(1)
All operations (push, pop, top, getMin) perform a fixed number of stack operations (append, pop, or peek) each taking constant time.
Space
O(n)
Two stacks are maintained, each potentially storing all elements in the worst case, resulting in O(n) auxiliary space proportional to the number of pushed elements.
Pattern Spotlight
Stack (Auxiliary Stack for State Tracking)
Maintain an auxiliary stack that mirrors the main stack's operations but stores the minimum value at each state, enabling constant-time retrieval of the minimum element by always keeping the current minimum at the top.
Solution
| 1 | class MinStack:
|
| 2 | def __init__(self):
|
| 3 | self.stack = []
|
| 4 | self.min_stack = []
|
| 5 |
|
| 6 | def push(self, val: int) -> None:
|
| 7 | self.stack.append(val)
|
| 8 | val = min(val, self.min_stack[-1] if self.min_stack else val)
|
| 9 | self.min_stack.append(val)
|
| 10 |
|
| 11 | def pop(self) -> None:
|
| 12 | self.stack.pop()
|
| 13 | self.min_stack.pop()
|
| 14 |
|
| 15 | def top(self) -> int:
|
| 16 | return self.stack[-1]
|
| 17 |
|
| 18 | def getMin(self) -> int:
|
| 19 | return self.min_stack[-1] |
Step-by-Step Solution
Maintain Parallel Stacks to Track Values and Minimums on Push
| 6 | def push(self, val: int) -> None:
|
| 7 | self.stack.append(val)
|
| 8 | val = min(val, self.min_stack[-1] if self.min_stack else val)
|
| 9 | self.min_stack.append(val)
|
Objective
To push the new value onto the main stack and update the min_stack with the current minimum after the push.
Key Insight
By pushing the minimum of the new value and the current minimum onto min_stack, the algorithm preserves the minimum element at every stack depth. This approach ensures that the top of min_stack always reflects the minimum of all elements below or equal to the current top of the main stack, enabling constant-time minimum retrieval.
Interview Quick-Check
Core Logic
Push the new value onto the main stack and push the minimum of the new value and the current minimum onto min_stack to maintain synchronized minimum tracking.
State & Boundaries
When min_stack is empty, the new value is the minimum by default.
Common Pitfalls & Bugs
Failing to update min_stack correctly leads to incorrect minimum values and breaks the O(1) getMin guarantee.
Synchronize Stack and Min_Stack on Pop to Maintain Consistency
To remove the top elements from both the main stack and min_stack, ensuring both remain aligned.
Retrieve the Top Element and Current Minimum in Constant Time
To return the top element of the main stack and the current minimum from min_stack efficiently.
2 more steps with full analysis available on Pro.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
val = min(val, self.min_stack[-1] if self.min_stack else val)Calculate the new minimum by comparing the pushed value with the current minimum.
This line ensures the min_stack always holds the minimum value up to the current stack depth by choosing the smaller between the new value and the existing minimum.
self.min_stack.pop()Pop the top element from the min_stack.
Removing the corresponding minimum value keeps min_stack aligned with the main stack, preserving correct minimum tracking.
return self.min_stack[-1]Return the top element of the min_stack, representing the current minimum.
Because min_stack mirrors the main stack's state with minimum values, its top element is always the current minimum, enabling O(1) retrieval.
Full line-by-line criticality + rationale for all 13 lines available on Pro.
Test Your Understanding
Why is it necessary to maintain a separate min_stack alongside the main stack?
See the answer with Pro.
Related Problems
Monotonic Stack pattern
Don't just read it. Drill it.
Reconstruct Min Stack from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Min Stack drill