How Would You Design a Min Stack?
Learn how to design a min stack with O(1) push, pop, top, and getMin using an auxiliary stack, with Python code.
Expected Interview Answer
A min stack supports push, pop, top, and getMin all in O(1) by maintaining a second, auxiliary stack that tracks the minimum value at each point in the main stack's history, so every push and pop keeps both stacks synchronized.
The core idea is that the current minimum only changes when you push a new value that is less than or equal to the current minimum, or when you pop a value that was the current minimum. A parallel min-stack captures this: on every push, you push the smaller of the new value and the current min-stack top onto the min-stack (or just push whenever the new value is less than or equal to the current min), and on every pop you pop both stacks together, which automatically restores the previous minimum. getMin then becomes a plain O(1) peek at the min-stack's top. A space-optimized variant stores only (value, current_min) pairs or deltas in a single stack to avoid a fully separate structure, but the auxiliary-stack idea is the one interviewers expect first.
- push, pop, top, and getMin are all O(1)
- No re-scanning needed to find the minimum after a pop
- Auxiliary stack stays perfectly synchronized with the main stack
- Extends naturally to a max stack or a stack tracking any running aggregate
AI Mentor Explanation
Imagine a team keeps a normal stack of individual innings scores as the season progresses, plus a second stack that always records the lowest score seen so far up to that point in the season. Every time a new innings score is pushed onto the main stack, the second stack also gets a push: either that same low score if it beats the previous record, or a repeat of the current record if it does not. If a season is undone by removing the most recent innings, popping both stacks together instantly reveals what the lowest score was before that innings happened, with no need to rescan the whole season. This paired-stack trick is exactly how a min stack answers 'what is the lowest value right now' in O(1) after any sequence of pushes and pops.
Step-by-Step Explanation
Step 1
Maintain two parallel stacks
A main stack for values, and a min-stack that tracks the running minimum at each depth.
Step 2
Push updates both stacks
Push the value onto main; push min(value, current min-stack top) onto the min-stack (or just the value if it is a new record).
Step 3
Pop removes from both together
Popping the main stack also pops the min-stack, automatically restoring the prior minimum.
Step 4
getMin peeks the min-stack
getMin() is O(1): just return the min-stack's top, no scanning required.
What Interviewer Expects
- Identify the auxiliary min-stack as the core technique
- Explain why popping must remove from both stacks together to stay in sync
- State that all four operations (push, pop, top, getMin) are O(1)
- Mention the space-optimized single-stack-of-pairs variant as a follow-up
Common Mistakes
- Only pushing onto the min-stack when a new minimum is found, then failing to pop it correctly on a non-minimum pop
- Recomputing the minimum by scanning the whole stack on every getMin call (O(n) instead of O(1))
- Forgetting to pop the min-stack in lockstep with the main stack
- Not handling ties correctly when duplicate minimum values are pushed and later popped
Best Answer (HR Friendly)
“I would keep a second stack alongside the main one that always tracks the current minimum. Every time I push a value, I also push the smaller of that value and the current minimum onto the second stack, and every time I pop, I pop both stacks together. That keeps the minimum always available instantly at the top of the second stack, without ever having to rescan.”
Code Example
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, value):
self.stack.append(value)
current_min = value if not self.min_stack else min(value, self.min_stack[-1])
self.min_stack.append(current_min)
def pop(self):
if not self.stack:
raise IndexError("pop from empty stack")
self.min_stack.pop()
return self.stack.pop()
def top(self):
return self.stack[-1]
def get_min(self):
return self.min_stack[-1]Follow-up Questions
- How would you reduce space usage by storing only deltas instead of a full parallel stack?
- How would you design a max stack using the same idea?
- How would you support getMin over a sliding window instead of the whole stack?
- How does this compare to computing running minimums with a monotonic queue?
MCQ Practice
1. What is the time complexity of getMin() in a properly designed min stack?
The min-stack top always holds the current minimum, so getMin is a plain O(1) peek.
2. When popping from a min stack, what must happen to keep it correct?
Popping both stacks in lockstep is what restores the correct prior minimum without any rescanning.
3. What value gets pushed onto the min-stack on every push operation?
Pushing min(new_value, current_min) keeps the min-stack in sync with the main stack at every depth.
Flash Cards
What auxiliary structure does a min stack use? — A second, parallel min-stack that tracks the running minimum at each depth of the main stack.
What is pushed onto the min-stack on each push? — The smaller of the new value and the current top of the min-stack.
What must happen on pop to keep the min stack correct? — Both the main stack and the min-stack must be popped together.
What are the time complexities of push, pop, top, and getMin? — All four are O(1).