Problem Statement
Design a stack that supports the following operations in O(1) time:
push(x)
pop()
top()
getMin()
getMin() should always return the minimum element currently present in the stack.
Brute Force Intuition
In an interview, you can explain it like this:
We can use a normal stack. Whenever
getMin()is called, simply traverse the entire stack and find the minimum element.
This works, but every getMin() requires scanning all elements.
Complexity
| Operation | Complexity |
|---|---|
| push | O(1) |
| pop | O(1) |
| top | O(1) |
| getMin | O(N) |
Brute Force Code
class MinStack {
Stack<Integer> st;
public MinStack() {
st = new Stack<>();
}
public void push(int val) {
st.push(val);
}
public void pop() {
st.pop();
}
public int top() {
return st.peek();
}
public int getMin() {
int min = Integer.MAX_VALUE;
for (int num : st) {
min = Math.min(min, num);
}
return min;
}
}
Moving Towards the Optimal Approach
The problem is:
Finding Minimum
Instead of searching every time,
why not store the minimum while inserting elements?
Maintain another stack that stores:
Current Minimum
at every stage.
Pattern Recognition
Whenever you see:
- Stack
- Current Minimum / Maximum
- O(1) Query
Think:
Two Stacks
Key Observation
Main Stack:
5
2
8
1
Min Stack:
5
2
2
1
Top of Min Stack always stores:
Minimum Element
Optimal Approach
Push
Push into main stack.
If:
Current element <= current minimum
also push into min stack.
Pop
If popped element equals:
Minimum
remove from min stack too.
getMin()
Simply return:
Top of Min Stack
Optimal Java Solution
class MinStack {
Stack<Integer> stack;
Stack<Integer> minStack;
public MinStack() {
stack = new Stack<>();
minStack = new Stack<>();
}
public void push(int val) {
stack.push(val);
if (minStack.isEmpty()
|| val <= minStack.peek()) {
minStack.push(val);
}
}
public void pop() {
if (stack.peek().equals(minStack.peek())) {
minStack.pop();
}
stack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
Dry Run
Operations
push(5)
Main Stack:
5
Min Stack:
5
push(2)
Main:
2
5
Min:
2
5
push(8)
Main:
8
2
5
Min:
2
5
Minimum:
2
push(1)
Main:
1
8
2
5
Min:
1
2
5
Minimum:
1
pop()
Remove:
1
Main:
8
2
5
Min:
2
5
Minimum:
2
Why Two Stacks Work?
Every minimum value is stored separately.
Whenever the minimum element is removed:
Remove it from Min Stack too.
Thus:
Top of Min Stack
=
Current Minimum
without scanning the stack.
Complexity Analysis
| Operation | Complexity |
|---|---|
| Push | O(1) |
| Pop | O(1) |
| Top | O(1) |
| Get Min | O(1) |
Follow-Up (Optimal Space)
Instead of maintaining two stacks,
we can use:
One Stack
+
One Variable (min)
using an encoding technique.
This reduces auxiliary space while keeping all operations O(1).
Interview One-Liner
Maintain a second stack that stores the minimum element seen so far. The top of the second stack always represents the current minimum.
Pattern Learned
Stack
+
Need Current Minimum
↓
Extra Stack
Similar Problems
- Min Stack
- Max Stack
- Stock Span
- Daily Temperatures
- Largest Rectangle in Histogram
Memory Trick
Think:
Push
↓
Is New Minimum?
↓
Yes
↓
Push into Min Stack
Pop
↓
Removing Minimum?
↓
Pop from Min Stack
Mental Model
Main Stack
Stores All Values
↓
Min Stack
Stores Running Minimum
Whenever you hear:
"Design a stack supporting getMin() in O(1)"
your brain should immediately think:
Two Stacks (Main Stack + Min Stack)