155. Min Stack
Asked at Oracle, Salesforce, Walmart, Snowflake
Difficulty
Medium
Time
O(1) for push, pop, top and getM
Space
O(n)
Pattern
Stack
Companies
4
Problem
Design a stack class called MinStack that works like a normal stack but can also report its smallest element at any time.
You must support four operations, and every one of them must run in O(1) time: push(val) puts a value on top, pop() removes the top value, top() returns the top value without removing it, and getMin() returns the smallest value currently in the stack.
The tricky part is getMin(). Scanning the whole stack each time would be O(n), which is too slow. The usual trick is to keep a second stack that tracks the minimum at each level. When you push a value that is less than or equal to the current minimum, you also push it onto the min stack. When you pop a value that equals the current minimum, you pop the min stack too. Then getMin() is just the top of the min stack.
Note that pop, top and getMin are only ever called when the stack is not empty, so you do not need to handle the empty case for those.
A stack that also knows its minimum
Constraints
- ●
-2^31 <= val <= 2^31 - 1 - ●
pop, top and getMin are only called on a non-empty stack - ●
At most 3 * 10^4 calls are made in total to push, pop, top and getMin
Examples
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]][null,null,null,null,-3,null,0,-2]["MinStack","push","push","getMin","pop","getMin"]
[[],[5],[1],[],[],[]][null,null,null,1,null,5]Asked At
4 companies| Company | Difficulty | |
|---|---|---|
| Oracle | Medium | View all Oracle questions → |
| Salesforce | Medium | View all Salesforce questions → |
| Walmart | Medium | View all Walmart questions → |
| Snowflake | Medium | View all Snowflake 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.
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).
Two stacks working together
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
O(1) for push, pop, top and getM timeclass 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 runs in O(1) for push, pop, top and getM time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Min Stack?
Min Stack is asked at Oracle, Salesforce, Walmart, Snowflake. 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.