Min Stack
Asked at Oracle, Salesforce, Walmart
Problem
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. Implement the MinStack class: MinStack() initializes the stack, push(val) pushes val, pop() removes the top element, top() gets the top element, getMin() retrieves the minimum element. All operations must run in O(1) time.
Asked At
| Company | Difficulty | |
|---|---|---|
| Oracle | Medium | View all Oracle questions → |
| Salesforce | Medium | View all Salesforce questions → |
| Walmart | Medium | View all Walmart questions → |
How to Think About It
Naive approach: on getMin, scan the entire stack. Time: O(n) for getMin. The problem requires O(1) for all operations.
Auxiliary stack approach: maintain a second min_stack that stores the minimum at each level. When pushing, also push the current minimum onto min_stack. When popping, pop from both stacks. getMin() just returns the top of min_stack.
The auxiliary stack invariant: min_stack.top() always holds the minimum of all elements currently in the main stack. When pushing a value <= current minimum, push it onto min_stack. When popping a value equal to the current minimum, also pop from min_stack.
Visual walkthrough for push(3), push(5), push(2), push(1), pop(), pop(), getMin():
push(3): stack=[3], min_stack=[3]
push(5): stack=[3,5], min_stack=[3] (5 > 3, don't push to min_stack)
push(2): stack=[3,5,2], min_stack=[3,2] (2 < 3)
push(1): stack=[3,5,2,1], min_stack=[3,2,1] (1 < 2)
pop(): stack=[3,5,2], min_stack=[3,2] (popped 1, which was min)
pop(): stack=[3,5], min_stack=[3] (popped 2, which was min)
getMin(): min_stack.top() = 3
Alternative: store (value, current_min) tuples in a single stack. Each element stores its value and the minimum at that point. Push: (val, min(val, stack.top().min)). This uses one stack but more space per element.
Time: O(1) for all operations. Space: O(n) for the auxiliary stack.
Optimal Approach
Two-stack approach:
stack: stores all values.min_stack: stores the minimum at each level.
push(val): push val to stack. If min_stack is empty or val <= min_stack.top(), push val to min_stack.
pop(): pop from stack. If the popped value == min_stack.top(), also pop from min_stack.
top(): return stack.top().
getMin(): return min_stack.top().
Walkthrough: push(3), push(5), push(2), push(1), pop(), pop(), getMin()
- push(3): stack=[3], min=[3]
- push(5): stack=[3,5], min=[3]
- push(2): stack=[3,5,2], min=[3,2]
- push(1): stack=[3,5,2,1], min=[3,2,1]
- pop(): stack=[3,5,2], min=[3,2]
- pop(): stack=[3,5], min=[3]
- getMin(): 3
Time: O(1) all ops. Space: O(n).
What Trips People Up in Real Interviews
Using < instead of <= when pushing to min_stack. If you push duplicate minimums, you need <= so that popping one minimum doesn't remove the other from min_stack. For example, push(2), push(2), pop() should leave min=2, not crash.
Not popping from min_stack when the popped value equals the current minimum. Forgetting this causes min_stack to grow unboundedly and return stale minimums.
Trying to use a single variable to track the minimum. This fails when the minimum is popped — you need to know the next minimum. The auxiliary stack handles this by remembering the minimum at each level.
Using getMin() to find the minimum by scanning. This is O(n). The whole point of the design is O(1) getMin() via the auxiliary stack.
Confusing top() with getMin(). top() returns the most recently pushed element. getMin() returns the smallest element. They are different operations that return different values.
Solution Code
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val):
self.stack.append(val)
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self):
val = self.stack.pop()
if val == self.min_stack[-1]:
self.min_stack.pop()
def top(self):
return self.stack[-1]
def getMin(self):
return self.min_stack[-1]Frequently Asked Questions
What is the Min Stack problem?
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. Implement the `MinStack` class: `MinStack()` initializes the stack, `push(val)` pushes val, `pop()` removes the top element, `top()` gets the top element, `getMin()` retrieves the minimum element. All operations must run in `O(1)` time.
How do you solve Min Stack?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Min Stack?
Min Stack is asked at Oracle, Salesforce, Walmart. It is a medium difficulty problem.
What are common mistakes on Min Stack?
- Using `<` instead of `<=` when pushing to `min_stack`. If you push duplicate minimums, you need `<=` so that popping one minimum doesn't remove the other from `min_stack`. For example, `push(2)`, `push(2)`, `pop()` should leave min=2, not crash.
- Not popping from `min_stack` when the popped value equals the current minimum. Forgetting this causes `min_stack` to grow unboundedly and return stale minimums.
- Trying to use a single variable to track the minimum. This fails when the minimum is popped — you need to know the next minimum. The auxiliary stack handles this by remembering the minimum at each level.
- Using `getMin()` to find the minimum by scanning. This is `O(n)`. The whole point of the design is `O(1)` `getMin()` via the auxiliary stack.
- Confusing `top()` with `getMin()`. `top()` returns the most recently pushed element. `getMin()` returns the smallest element. They are different operations that return different values.