The Min Stack problem is a classic design question that tests whether you can augment a data structure while preserving its original operations.
Problem
Design a stack that supports the following operations, all in O(1) time:
push(val)– Push an element onto the stack.pop()– Remove the top element.top()– Return the top element.getMin()– Return the minimum element currently in the stack.
Example
Input:
["MinStack", "push", 1, "push", 2, "push", 0, "getMin", "pop", "top", "getMin"]
Output:
[null, null, null, null, 0, null, 2, 1]Initial Thought
A normal stack easily supports push, pop, and top in O(1) time.
The challenge is implementing getMin() in O(1).
A naive approach would be to scan the entire stack every time getMin() is called.
min(stack)Unfortunately, this takes O(n) time, which violates the problem’s constraints.
So we need a way to always know the current minimum without searching the stack.
Key Idea: Maintain a Second Stack
Instead of storing only the values, we maintain another stack that tracks the minimum value at every level.
We use:
stack→ stores all values normally.minStack→ stores the minimum value seen up to each position.
For every push, we compare the new value with the current minimum.
currentMin = min(val, minStack[-1])Then we push this minimum onto minStack.
This means both stacks always have the same size.
Visual Example
Let’s push:
push(3)
push(5)
push(2)
push(4)Stack | Min Stack |
|---|---|
3 | 3 |
3, 5 | 3, 3 |
3, 5, 2 | 3, 3, 2 |
3, 5, 2, 4 | 3, 3, 2, 2 |
Notice something interesting:
Even though we pushed 4, the minimum is still 2.
So instead of pushing 4 into minStack, we push the current minimum again.
The top of minStack always tells us the minimum element of the stack.
What Happens When We Pop?
Suppose we pop 4.
Stack:
3, 5, 2
Min Stack:
3, 3, 2The minimum is still 2.
If we pop again:
Stack:
3, 5
Min Stack:
3, 3Now the minimum automatically becomes 3.
No recalculation is needed because minStack has been tracking the minimum at every level.
Algorithm
Push
- Push the value onto the main stack.
- Compare it with the current minimum.
- Push the smaller value onto
minStack.
Pop
Pop from both stacks.
Top
Return the top of the main stack.
getMin
Return the top of minStack.
Every operation only touches the top of one or two stacks, so each operation runs in O(1) time.
Python Solution
class MinStack:
def __init__(self):
self.stack = []
self.minstack = []
def push(self, val: int) -> None:
self.stack.append(val)
if self.minstack:
val = min(val, self.minstack[-1])
self.minstack.append(val)
def pop(self) -> None:
self.stack.pop()
self.minstack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.minstack[-1]Why This Works
The clever trick is that minStack doesn’t necessarily store the values being pushed.
Instead, it stores the minimum value up to that point.
For example:
Values pushed:
5 2 8 1 6
Main Stack:
5 2 8 1 6
Min Stack:
5 2 2 1 1At every index, minStack[i] represents the minimum of all elements from stack[0] to stack[i].
So the current minimum is always available at the top.
Complexity Analysis
Operation | Time | Space |
|---|---|---|
push | O(1) | O(1) |
pop | O(1) | O(1) |
top | O(1) | O(1) |
getMin | O(1) | O(1) |
Overall extra space is O(n) because minStack stores one entry for each element in the main stack.
Final Thoughts
The key insight isn’t about finding the minimum quickly—it’s about remembering the minimum as the stack evolves.
By maintaining a second stack that mirrors the main stack and stores the minimum value at every level, we eliminate the need to recompute the minimum after every pop().
This pattern of maintaining an auxiliary data structure alongside the main one is common in data structure design and is a useful technique to recognize for future interview problems.
