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
The 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. When popping, pop from both stacks. This ensures getMin simply returns the top of min_stack in O(1) time.
Optimal Approach
Use 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. On pop, remove the top elements from both stacks. top returns the top of stack, and getMin returns the top of min_stack. This guarantees all operations run in constant time.
Time
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] |
| 1 | import java.util.ArrayDeque; |
| 2 | import java.util.Deque; |
| 3 | |
| 4 | public class MinStack { |
| 5 | private Deque<Integer> stack; |
| 6 | private Deque<Integer> minStack; |
| 7 | |
| 8 | public MinStack() { |
| 9 | stack = new ArrayDeque<>(); |
| 10 | minStack = new ArrayDeque<>(); |
| 11 | } |
| 12 | |
| 13 | public void push(int val) { |
| 14 | stack.push(val); |
| 15 | int currentMin = minStack.isEmpty() ? val : Math.min(val, minStack.peek()); |
| 16 | minStack.push(currentMin); |
| 17 | } |
| 18 | |
| 19 | public void pop() { |
| 20 | stack.pop(); |
| 21 | minStack.pop(); |
| 22 | } |
| 23 | |
| 24 | public int top() { |
| 25 | return stack.peek(); |
| 26 | } |
| 27 | |
| 28 | public int getMin() { |
| 29 | return minStack.peek(); |
| 30 | } |
| 31 | } |
| 1 | #include <stack> |
| 2 | #include <algorithm> |
| 3 | |
| 4 | using namespace std; |
| 5 | |
| 6 | class MinStack { |
| 7 | private: |
| 8 | std::stack<int> stack; |
| 9 | std::stack<int> min_stack; |
| 10 | |
| 11 | public: |
| 12 | MinStack() { |
| 13 | } |
| 14 | |
| 15 | void push(int val) { |
| 16 | stack.push(val); |
| 17 | int current_min = min_stack.empty() ? val : std::min(val, min_stack.top()); |
| 18 | min_stack.push(current_min); |
| 19 | } |
| 20 | |
| 21 | void pop() { |
| 22 | stack.pop(); |
| 23 | min_stack.pop(); |
| 24 | } |
| 25 | |
| 26 | int top() { |
| 27 | return stack.top(); |
| 28 | } |
| 29 | |
| 30 | int getMin() { |
| 31 | return min_stack.top(); |
| 32 | } |
| 33 | }; |
| 1 | class MinStack { |
| 2 | constructor() { |
| 3 | this.stack = []; |
| 4 | this.minStack = []; |
| 5 | } |
| 6 | |
| 7 | push(val) { |
| 8 | this.stack.push(val); |
| 9 | const currentMin = this.minStack.length === 0 ? val : Math.min(val, this.minStack[this.minStack.length - 1]); |
| 10 | this.minStack.push(currentMin); |
| 11 | } |
| 12 | |
| 13 | pop() { |
| 14 | this.stack.pop(); |
| 15 | this.minStack.pop(); |
| 16 | } |
| 17 | |
| 18 | top() { |
| 19 | return this.stack[this.stack.length - 1]; |
| 20 | } |
| 21 | |
| 22 | getMin() { |
| 23 | return this.minStack[this.minStack.length - 1]; |
| 24 | } |
| 25 | } |
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
| 11 | def pop(self) -> None:
|
| 12 | self.stack.pop()
|
| 13 | self.min_stack.pop()
|
Objective
To remove the top elements from both the main stack and min_stack, ensuring both remain aligned.
Key Insight
Popping from both stacks simultaneously maintains the invariant that min_stack's top always corresponds to the minimum of the current main stack. This synchronization prevents stale minimum values from persisting after elements are removed.
Interview Quick-Check
Core Logic
Pop from both stacks to keep the minimum tracking aligned with the current stack state.
State & Boundaries
Pop operations assume the stack is non-empty, as per problem constraints.
Common Pitfalls & Bugs
Popping only from the main stack without updating min_stack causes getMin to return incorrect results.
Retrieve the Top Element and Current Minimum in Constant Time
| 15 | def top(self) -> int:
|
| 16 | return self.stack[-1]
|
| 18 | def getMin(self) -> int:
|
| 19 | return self.min_stack[-1] |
Objective
To return the top element of the main stack and the current minimum from min_stack efficiently.
Key Insight
Because min_stack mirrors the main stack's state with minimum values, the top of min_stack always holds the current minimum. Accessing the last element of a list is O(1), so both top and getMin operations run in constant time.
Interview Quick-Check
Core Logic
Return the last element of stack for top and the last element of min_stack for getMin, both in O(1) time.
State & Boundaries
These operations assume the stack is non-empty, consistent with problem constraints.
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.
self.min_stack = []Initialize the min_stack as an empty list.
The min_stack tracks the minimum element at each stack depth, enabling constant-time minimum retrieval.
self.min_stack.append(val)Append the current minimum to the min_stack.
By pushing the current minimum onto min_stack, the algorithm maintains a parallel structure that tracks minimums at every stack level.
self.stack = []Initialize the main stack as an empty list.
The main stack stores all pushed values, enabling standard stack operations with O(1) append and pop.
self.stack.append(val)Append the new value to the main stack.
This adds the element to the stack in O(1) time, preserving the LIFO order.
self.stack.pop()Pop the top element from the main stack.
Removing the top element maintains the stack's LIFO behavior.
return self.stack[-1]Return the top element of the main stack.
Accessing the last element of the list returns the current top in O(1) time, consistent with stack semantics.
def push(self, val: int) -> None:Define the push method to add a value to the stack.
This method encapsulates the logic for inserting elements while maintaining minimum tracking.
def pop(self) -> None:Define the pop method to remove the top element.
This method ensures both stacks remain synchronized when elements are removed.
def top(self) -> int:Define the top method to retrieve the top element.
This method provides access to the most recently pushed element without modifying the stack.
def getMin(self) -> int:Define the getMin method to retrieve the current minimum.
This method exposes the minimum element in the stack at any time in constant time.
Test Your Understanding
Why is it necessary to maintain a separate min_stack alongside the main stack?
Because the minimum element can change with each push or pop, the min_stack keeps track of the minimum at every stack level, allowing getMin to return the current minimum in O(1) time without scanning the entire stack.
Related Problems
Stacks 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