108. Min Stack
🔗 LeetCode Problem: 155. Min Stack
📊 Difficulty: Medium
🏷️ Topics: Stack, Design
Problem Statement
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Implement the MinStack class:
MinStack()initializes the stack object.void push(int val)pushes the elementvalonto the stack.void pop()removes the element on the top of the stack.int top()gets the top element of the stack.int getMin()retrieves the minimum element in the stack.
You must implement a solution with O(1) time complexity for each function.
Example 1:
Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output
[null,null,null,null,-3,null,0,-2]
Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top(); // return 0
minStack.getMin(); // return -2
Constraints:
- -2^31 <= val <= 2^31 - 1
- Methods pop, top and getMin operations will always be called on non-empty stacks.
- At most 3 * 10^4 calls will be made to push, pop, top, and getMin.
🌟 ELI5: The Simple Idea!
The Challenge:
Regular stack: Easy to get top element
push(5) → [5]
push(3) → [5, 3]
top() → 3 ✓
But how to get minimum in O(1)?
Naive: Scan entire stack → O(n) ✗
Need: Track minimum somehow → O(1) ✓
The Insight:
Track minimum at each level!
Stack: [5, 3, 7, 2, 8]
Min at: [5, 3, 3, 2, 2]
↑ ↑ ↑ ↑ ↑
When When When When When
only 5 3 7 2 8
5 added added added added
At ANY point, we know the current minimum!
🎨 Visual Understanding
Example Walkthrough
Operation: push(-2)
Stack: [-2]
Min: [-2]
getMin() → -2 ✓
Operation: push(0)
Stack: [-2, 0]
Min: [-2, -2]
Previous min was -2, still -2
getMin() → -2 ✓
Operation: push(-3)
Stack: [-2, 0, -3]
Min: [-2, -2, -3]
New minimum is -3
getMin() → -3 ✓
Operation: pop()
Stack: [-2, 0]
Min: [-2, -2]
After removing -3, min reverts to -2
getMin() → -2 ✓
Operation: top()
Returns: 0 (top of stack)
Operation: getMin()
Returns: -2 (minimum in stack)
🎯 Approach 1: Two Stacks ⭐⭐
The Standard Solution
Algorithm:
Use two stacks:
1. mainStack: stores all elements
2. minStack: stores minimum at each level
Operations:
push(x):
- Push x to mainStack
- Push min(x, currentMin) to minStack
pop():
- Pop from both stacks
top():
- Return mainStack.top()
getMin():
- Return minStack.top()
Implementation
/**
* Two-stack approach
* Time: O(1) for all operations
* Space: O(n) for both stacks
*/
class MinStack {
private Stack<Integer> stack;
private Stack<Integer> minStack;
public MinStack() {
stack = new Stack<>();
minStack = new Stack<>();
}
public void push(int val) {
stack.push(val);
// Push current minimum to minStack
if (minStack.isEmpty()) {
minStack.push(val);
} else {
minStack.push(Math.min(val, minStack.peek()));
}
}
public void pop() {
stack.pop();
minStack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
⏰ Time: O(1) for all operations
💾 Space: O(n) - Two stacks
🔍 Super Detailed Dry Run
Example: Operations from problem
═══════════════════════════════════════════════════════════════
Initialization
═══════════════════════════════════════════════════════════════
MinStack minStack = new MinStack();
stack = []
minStack = []
═══════════════════════════════════════════════════════════════
Operation 1: push(-2)
═══════════════════════════════════════════════════════════════
Input: val = -2
Check: Is minStack empty? Yes
Action:
stack.push(-2)
minStack.push(-2) // First element, so it's the min
State:
stack: [-2]
minStack: [-2]
Current minimum: -2
═══════════════════════════════════════════════════════════════
Operation 2: push(0)
═══════════════════════════════════════════════════════════════
Input: val = 0
Check: Is minStack empty? No
Action:
stack.push(0)
Compare: Math.min(0, minStack.peek())
= Math.min(0, -2)
= -2
minStack.push(-2)
State:
stack: [-2, 0]
minStack: [-2, -2]
↑ ↑
When When
-2 0
added added
Current minimum: -2 (stays the same)
═══════════════════════════════════════════════════════════════
Operation 3: push(-3)
═══════════════════════════════════════════════════════════════
Input: val = -3
Check: Is minStack empty? No
Action:
stack.push(-3)
Compare: Math.min(-3, minStack.peek())
= Math.min(-3, -2)
= -3
minStack.push(-3)
State:
stack: [-2, 0, -3]
minStack: [-2, -2, -3]
↑ ↑ ↑
When When When
-2 0 -3
added added added
Current minimum: -3 (new minimum!)
═══════════════════════════════════════════════════════════════
Operation 4: getMin()
═══════════════════════════════════════════════════════════════
Action:
return minStack.peek()
return -3
State unchanged:
stack: [-2, 0, -3]
minStack: [-2, -2, -3]
Return: -3 ✓
═══════════════════════════════════════════════════════════════
Operation 5: pop()
═══════════════════════════════════════════════════════════════
Action:
stack.pop() // Removes -3
minStack.pop() // Removes -3
State:
stack: [-2, 0]
minStack: [-2, -2]
Current minimum: -2 (reverts to previous min!)
Explanation:
Both stacks pop together
Minimum automatically updates to previous level
═══════════════════════════════════════════════════════════════
Operation 6: top()
═══════════════════════════════════════════════════════════════
Action:
return stack.peek()
return 0
State unchanged:
stack: [-2, 0]
minStack: [-2, -2]
Return: 0 ✓
═══════════════════════════════════════════════════════════════
Operation 7: getMin()
═══════════════════════════════════════════════════════════════
Action:
return minStack.peek()
return -2
State unchanged:
stack: [-2, 0]
minStack: [-2, -2]
Return: -2 ✓
🎯 Approach 2: Single Stack with Pairs ⭐
Space-Optimized (Conceptually)
/**
* Store pairs: (value, currentMin)
* Time: O(1), Space: O(n)
*/
class MinStack {
private Stack<int[]> stack; // Each entry: [value, min]
public MinStack() {
stack = new Stack<>();
}
public void push(int val) {
if (stack.isEmpty()) {
stack.push(new int[]{val, val});
} else {
int currentMin = stack.peek()[1];
stack.push(new int[]{val, Math.min(val, currentMin)});
}
}
public void pop() {
stack.pop();
}
public int top() {
return stack.peek()[0];
}
public int getMin() {
return stack.peek()[1];
}
}
Using Custom Node Class
class MinStack {
private class Node {
int value;
int min;
Node next;
Node(int value, int min, Node next) {
this.value = value;
this.min = min;
this.next = next;
}
}
private Node head;
public MinStack() {
head = null;
}
public void push(int val) {
if (head == null) {
head = new Node(val, val, null);
} else {
head = new Node(val, Math.min(val, head.min), head);
}
}
public void pop() {
head = head.next;
}
public int top() {
return head.value;
}
public int getMin() {
return head.min;
}
}
🎯 Why This Solution Works
The Key Insight
Why track min at each level?
Stack state changes only on push/pop:
Push: New element might be new minimum
Track: What's minimum INCLUDING this element?
Pop: Removed element might be the minimum
Need: What was minimum BEFORE this element?
By storing min at each level:
✓ Always know current minimum (O(1))
✓ When pop, automatically restore previous min
✓ No need to search (no O(n))
Visual Understanding
Consider: push(5), push(3), push(7), push(2)
Without min tracking:
Stack: [5, 3, 7, 2]
getMin()? Must scan: O(n) ✗
With min tracking:
Stack: [5, 3, 7, 2]
Min: [5, 3, 3, 2]
getMin()? Just peek minStack: O(1) ✓
After pop():
Stack: [5, 3, 7]
Min: [5, 3, 3]
getMin()? Still O(1), automatically correct!
Why Both Stacks Pop Together
Critical: main and min must stay synchronized!
If only mainStack pops:
Stack: [5, 3, 7] (correct)
Min: [5, 3, 3, 2] (WRONG! Still has 2)
getMin() → 2 ✗ (but 2 is not in stack!)
When both pop together:
Stack: [5, 3, 7] (correct)
Min: [5, 3, 3] (correct)
getMin() → 3 ✓
They're a team - must stay in sync!
⚠️ Common Mistakes
Mistake 1: Storing only one min value
// ❌ WRONG - Lost previous minimum after pop!
private int currentMin;
public void push(int val) {
stack.push(val);
currentMin = Math.min(val, currentMin);
}
public void pop() {
stack.pop();
// How to restore previous min? ✗
}
// ✓ CORRECT - Track min at each level
private Stack<Integer> minStack;
// Automatically restores on pop!
Mistake 2: Not handling empty minStack
// ❌ WRONG - Crashes on first push!
public void push(int val) {
stack.push(val);
minStack.push(Math.min(val, minStack.peek())); // peek() on empty!
}
// ✓ CORRECT - Check first
public void push(int val) {
stack.push(val);
if (minStack.isEmpty()) {
minStack.push(val);
} else {
minStack.push(Math.min(val, minStack.peek()));
}
}
Mistake 3: Only pushing when new minimum found
// ❌ WRONG - Stacks become unsynchronized!
public void push(int val) {
stack.push(val);
if (val < minStack.peek()) {
minStack.push(val); // Only sometimes push
}
}
// Now stacks have different sizes!
// ✓ CORRECT - Always push to both
public void push(int val) {
stack.push(val);
minStack.push(Math.min(val, minStack.peek()));
}
Mistake 4: Returning wrong stack for operations
// ❌ WRONG - Returning from wrong stack!
public int top() {
return minStack.peek(); // Returns min, not top!
}
// ✓ CORRECT
public int top() {
return stack.peek(); // Main stack for values
}
public int getMin() {
return minStack.peek(); // Min stack for minimum
}
🎯 Pattern Recognition
Problem Type: Data Structure Design
Core Pattern: Stack Pattern 5 - State Tracking
When to Apply:
✓ Need O(1) access to aggregate info
✓ Maintain historical state
✓ Track metadata alongside data
✓ Design problems with efficiency constraints
Recognition Keywords:
- "design a stack"
- "retrieve in constant time"
- "O(1) operations"
- "getMin" / "getMax"
- "maintain" something
Similar Problems:
- Max Stack (LC 716) - Same but maximum
- Stack with Increment (LC 1381)
- Min Stack II (follow-up optimizations)
Key Components:
┌────────────────────────────────────────────┐
│ Two stacks: main + auxiliary │
│ Main: stores actual values │
│ Auxiliary: stores metadata (min/max) │
│ Synchronized: push/pop both together │
│ getMin: O(1) peek auxiliary stack │
│ All operations: O(1) │
└────────────────────────────────────────────┘
🧠 Interview Strategy
Step 1: "I need O(1) for all operations"
Step 2: "I'll track minimum at each stack level"
Step 3: "Use two synchronized stacks"
Key Points to Mention:
- Two stacks: main for values, min for minimums
- On push: always push to both stacks
Main gets value, min gets min(value, currentMin)
- On pop: pop from both (stay synchronized)
- getMin: just peek min stack
- All operations: O(1)
Walk Through Example:
"For push(-2), push(0), push(-3):
After -2: stack=[-2], min=[-2]
After 0: stack=[-2,0], min=[-2,-2]
After -3: stack=[-2,0,-3], min=[-2,-2,-3]
getMin() returns minStack.peek() = -3"
Why Two Stacks:
"Need to track what minimum was at each level.
When pop removes current min, must know previous min.
Second stack stores this history.
Both stacks pop together to stay synchronized."
Space Tradeoff:
"Using O(n) extra space for O(1) time.
This is optimal - can't do better than O(1) time.
Space tradeoff is acceptable."
Edge Cases to Mention:
✓ Empty stack (handled by isEmpty checks)
✓ Single element (becomes both value and min)
✓ Duplicate minimums (handled correctly)
✓ All same values (all stored in min stack)
📝 Quick Revision Notes
🎯 Core Concept:
Min Stack: Use two synchronized stacks. Main stack stores values, min stack stores minimum at each level. Push: add to both (min gets Math.min(val, currentMin)). Pop: remove from both. getMin: peek min stack in O(1).
⚡ Quick Implementation:
import java.util.Stack;
// // Approach 1 - using 2 stacks. One is original stack and while other is min stack.
// class MinStack {
// Stack<Integer> stack;
// Stack<Integer> minStack;
// public MinStack() {
// stack = new Stack<>();
// minStack = new Stack<>();
// }
// public void push(int val) {
// // simply push the incoming value to stack (normal).
// stack.push(val);
// // for pushing to min stack which maintains min values maintained till
// // the level where above value gets pushed.
// if(minStack.isEmpty()) {
// minStack.push(val); // simply push if empty
// } else {
// // CRITICAL: since we are maintaining equal size stacks, we need to push min value in either case.
// minStack.push(Math.min(val, minStack.peek()));
// }
// }
// public void pop() {
// // Since we are pushing to both stacks, we need to pop from both.
// stack.pop();
// minStack.pop();
// }
// public int top() {
// return stack.peek();
// }
// public int getMin() {
// return minStack.peek();
// }
// }
// Approach 2 - using 1 stack.
class MinStack {
// 2 sized array. 1st element maintains actual value
// While 2nd element maintains min value (as we had minstack earlier)
Stack<int[]> stack;
public MinStack() {
stack = new Stack<>();
}
public void push(int val) {
if(stack.empty()) {
stack.push(new int[] {val, val});
} else {
stack.push(new int[] {val, Math.min(val, stack.peek()[1])});
}
}
public void pop() {
stack.pop();
}
public int top() {
return stack.peek()[0];
}
public int getMin() {
return stack.peek()[1];
}
}
class Solution {
public static void main(String[] args) {
MinStack ms = new MinStack();
ms.push(-2);
ms.push(0);
ms.push(-3);
System.out.println(ms.getMin() == -3);
ms.pop();
System.out.println(ms.top() == 0);
System.out.println(ms.getMin() == -2);
}
}
🔑 Key Insights:
- Pattern: Stack Pattern 5 (State Tracking)
- Two stacks: Main + Min (synchronized)
- Push both: Main gets val, min gets Math.min
- Pop both: Must stay in sync
- getMin: Just peek min stack
- All ops: O(1) time, O(n) space ✓
🎪 Memory Aid:
"Two stacks sync, min tracks history!"
"Push both, pop both, peek for min!" ✨
⚠️ Critical Rules:
Rule 1: ALWAYS push to both stacks
Not just when new minimum found
Keeps stacks synchronized
Rule 2: ALWAYS pop from both stacks
Even if not minimum being removed
Maintains synchronization
Rule 3: Check empty on first push
if (minStack.isEmpty())
minStack.push(val);
else
minStack.push(Math.min(val, minStack.peek()));
🧪 Edge Cases
Case 1: Single element
push(5)
stack: [5]
minStack: [5]
getMin() → 5 ✓
Case 2: Descending order
push(5), push(3), push(1)
stack: [5, 3, 1]
minStack: [5, 3, 1]
Each new element is minimum
Case 3: Ascending order
push(1), push(3), push(5)
stack: [1, 3, 5]
minStack: [1, 1, 1]
First element stays minimum
Case 4: Duplicate minimums
push(2), push(2), push(2)
stack: [2, 2, 2]
minStack: [2, 2, 2]
Correctly tracks all
Case 5: Pop minimum
Initial: stack=[3,1,5], min=[3,1,1]
pop() → stack=[3,1], min=[3,1]
getMin() → 1 ✓ (still correct)
All handled correctly! ✓
🎓 Complexity Analysis
Time Complexity: O(1)
All operations: O(1)
push(val): O(1)
- stack.push(): O(1)
- minStack.push(): O(1)
- Math.min(): O(1)
pop(): O(1)
- stack.pop(): O(1)
- minStack.pop(): O(1)
top(): O(1)
- stack.peek(): O(1)
getMin(): O(1)
- minStack.peek(): O(1)
Every operation is constant time! ✓
Space Complexity: O(n)
Two stacks:
- main stack: O(n)
- min stack: O(n)
Total: O(2n) = O(n) ✓
Tradeoff:
Extra O(n) space for O(1) time
This is optimal!
Can't do better:
To get min in O(1), must store it
Must track at each level for pop
📚 Related Problems
Same Pattern: - Max Stack (LC 716) - Track maximum - Moving Average from Data Stream (LC 346) - LRU Cache (LC 146) - Different but design problem
Design Problems: - LFU Cache (LC 460) - Implement Queue using Stacks (LC 232) - Implement Stack using Queues (LC 225)
Happy practicing! 🎯
Note: This problem teaches Stack Pattern 5: State Tracking! Master this and you understand: (1) auxiliary data structure design, (2) synchronized state management, (3) time-space tradeoffs, (4) O(1) aggregate operations. This pattern is fundamental for system design and appears in cache implementations, streaming algorithms, and more. Very common at Amazon, Meta, Google, Apple! 💪✨