Min Stack
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Design a stack that supports push, pop, top and getMin (the smallest value) all in O(1).
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1Scanning the stack for the minimum is O(n). What could you save at push time?
- Hint 2The minimum of the stack with this item on top = smaller of (this item, the minimum before it).
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
A pile of plates where, when you place a plate, you stick a label on it: "the smallest number in this whole pile so far is ...". Asking for the minimum is just reading the label on the top plate. Removing the top plate also removes its label, and the label on the plate beneath it is automatically correct again.
- The obvious way
Loop over all items on every getMin: O(n).
- The key insight
Store each item together with the minimum of everything at or below it. A push computes min(new value, previous top's minimum). Then getMin reads the top's saved minimum, and pop needs no repair because the item below already carries its own correct minimum.
- The algorithm
- Each stack entry is a pair: (value, minimum so far).
- push(x): new minimum = x if the stack is empty, else the smaller of x and the top's minimum.
- pop(): remove the top pair. top(): read its value.
- getMin(): read the top pair's minimum.
Watch it run
Examplepush(-2), push(0), push(-3), getMin(), pop(), top(), getMin()
push -2: it is the first plate, its label says min = -2.
plates: (-2, min -2)
Where people slip
- Do not keep one single "min" variable: after popping the minimum you would not know the next one.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
class MinStack:
def __init__(self):
self.plates = [] # (value, smallest so far)
def push(self, value):
smallest = value if not self.plates else min(value, self.plates[-1][1])
self.plates.append((value, smallest))
def pop(self):
self.plates.pop()
def top(self):
return self.plates[-1][0]
def getMin(self):
return self.plates[-1][1]Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.