Min Stack
Build a stack that can also tell you its smallest value in one step, at any moment.
- Auxiliary stack (running min)
- Design a data structure
Before this, know: What a stack is (push, pop, peek), Classes and methods (class in JavaScript and Python)
This one is different from most problems: instead of writing one function, you write a whole class. A class is a blueprint for an object that keeps its own data between calls (here, the stack) and has several methods (functions that belong to the object). This kind of problem is called a design problem.
Your MinStack class needs five things:
MinStack(): the constructor. It runs once, when the object is created, and sets up empty storage.push(val): putvalon top of the stack.pop(): remove the top item. It returns nothing.top(): return the top item without removing it.getMin(): return the smallest value currently in the stack.
The catch: every one of them must take O(1) time, meaning a fixed number of
steps no matter how many items are on the stack. That’s easy for the first four.
getMin is the hard part.
LeetCode doesn’t call a function once. It gives you two lists: the method names to call, in order, and the arguments for each call:
["MinStack", "push", "push", "push", "getMin", "pop", "top", "getMin"][[], [-2], [0], [-3], [], [], [], []]
Its test code reads them in pairs and does this:
const obj = new MinStack(); // "MinStack", []obj.push(-2); // "push", [-2]obj.push(0); // "push", [0]obj.push(-3); // "push", [-3]obj.getMin(); // returns -3obj.pop();obj.top(); // returns 0obj.getMin(); // returns -2
It collects what each call returns (null for calls that return nothing) and
compares with the expected output: [null, null, null, null, -3, null, 0, -2].
- -2
- 0
- -3
- -2
- 0
LeetCode promises pop, top and getMin are only called on a non-empty stack,
and there are at most 30,000 calls.
The trick is that a stack only changes at the top. So the “smallest value so far” at each height never changes once it’s written: removing the top can never change what was true about the items underneath.
Pause and think
After each push the minimum is 4, 4, 1, 1. After popping twice the stack is
[4, 6] and the minimum is 4.
You don’t need to look: it was already the minimum written down when the stack
was exactly [4, 6]. That’s the whole idea of this problem.
Keep one normal stack. push, pop and top are easy. For getMin, walk
through every item and remember the smallest one.
Brute force: getMin scans the whole stack
push(5), push(2), push(8), push(3), getMin(), pop(), getMin()
- 5
- call
- push(5)
- smallest
- —
- returns
- —
- items looked at (total)
- 0
- Looking at
- Smallest so far
push(5): put it on top. Fast.
Which line is running?
class MinStack { constructor() { this.stack = []; } push(val) {Running now: this.stack.push(val); } pop() { this.stack.pop(); } top() { return this.stack.at(-1); } getMin() { let smallest = Infinity; for (const x of this.stack) { smallest = Math.min(smallest, x); // look at EVERY item } return smallest; }}Brute force: getMin scans everything
class MinStack { constructor() { this.stack = []; } push(val) { this.stack.push(val); } pop() { this.stack.pop(); } top() { return this.stack.at(-1); } getMin() { let smallest = Infinity; for (const x of this.stack) { smallest = Math.min(smallest, x); // look at EVERY item } return smallest; }}class MinStack: def __init__(self): self.stack = [] def push(self, val): self.stack.append(val) def pop(self): self.stack.pop() def top(self): return self.stack[-1] def getMin(self): smallest = float("inf") for x in self.stack: smallest = min(smallest, x) # look at EVERY item return smallestthis.stack.at(-1) (JavaScript) and self.stack[-1] (Python) both mean “the last
item”, which is the top of the stack.
getMin looks at every item, every time it’s called. With 4 items that’s 4
looks. With 15,000 items pushed and then 15,000 getMin calls, that’s
15,000 × 15,000 = 225,000,000 looks. A single getMin is
O(n), and the problem explicitly
asks for O(1).
An auxiliary stack is a helper stack that rides along with the main one. For every value we push, we also push a note on the helper: “the smallest value from the bottom up to here”.
Pattern
Auxiliary stack (running min or max)
Use it when: you need the minimum or maximum of a stack (or anything that only changes at one end) at any moment, in O(1).
Signal words
- “design a stack”
- “retrieve the minimum in constant time”
- “getMin”
- “max stack”
- “O(1) each operation”
- In the constructor, create two empty stacks:
stackfor the values andminsfor the running minimum. push(val): pushvalonstack. Work out the new minimum: the smaller ofvaland the old minimum (the top ofmins). Ifminsis empty, the new minimum is justval. Push that onmins.pop(): pop both stacks. They always stay the same height.top(): return the top ofstack.getMin(): return the top ofmins.
Press Play. Watch the two stacks grow and shrink together, and notice that
getMin never searches: it just reads the top of mins. The “repeated minimum”
example shows why we push a copy of the minimum even when it doesn’t change.
Two stacks side by side
push(5), push(2), push(8), getMin(), pop(), pop(), getMin()
- empty
- empty
- call
- new MinStack()
- returns
- —
- null
- Just pushed
- Previous minimum
- Value returned
LeetCode first creates the object. Our MinStack starts with two empty stacks: "stack" holds the values, "mins" holds the smallest value seen so far at each height.
Which line is running?
class MinStack { constructor() { this.stack = [];Running now: this.mins = []; // mins[i] = smallest value in stack[0..i] } push(val) { this.stack.push(val); const prevMin = this.mins.length > 0 ? this.mins.at(-1) : val; this.mins.push(Math.min(val, prevMin)); } pop() { this.stack.pop(); this.mins.pop(); // the two stacks always shrink together } top() { return this.stack.at(-1); } getMin() { return this.mins.at(-1); }}Two stacks
class MinStack { constructor() { this.stack = []; this.mins = []; // mins[i] = smallest value in stack[0..i] } push(val) { this.stack.push(val); const prevMin = this.mins.length > 0 ? this.mins.at(-1) : val; this.mins.push(Math.min(val, prevMin)); } pop() { this.stack.pop(); this.mins.pop(); // the two stacks always shrink together } top() { return this.stack.at(-1); } getMin() { return this.mins.at(-1); }}class MinStack: def __init__(self): self.stack = [] self.mins = [] # mins[i] = smallest value in stack[0..i] def push(self, val): self.stack.append(val) prev_min = self.mins[-1] if self.mins else val self.mins.append(min(val, prev_min)) def pop(self): self.stack.pop() self.mins.pop() # the two stacks always shrink together def top(self): return self.stack[-1] def getMin(self): return self.mins[-1]The two versions have the same shape. JavaScript’s closing } lines make its
line numbers run a little ahead; we give both when they differ.
- Line 1:
class MinStackstarts the blueprint. LeetCode gives you exactly this skeleton with empty methods; you fill them in. - Lines 2–4: the constructor (
constructor()in JavaScript,__init__(self)in Python) runs once when LeetCode doesnew MinStack()/MinStack().this./self.means “this object’s own”, so the two arrays live as long as the object. - Line 8 (JS) / line 7 (Py): a normal push onto the value stack.
- Line 9 (JS) / line 8 (Py): the previous minimum is the top of
mins. Ifminsis empty (this is the first push), there is no previous minimum, so we usevalitself.cond ? a : b(JS) anda if cond else b(Py) both mean “if cond then a, otherwise b”. - Line 10 (JS) / line 9 (Py): push the smaller of the two.
Math.min/minreturn the smaller of their arguments. - Lines 14–15 (JS) / 12–13 (Py): pop both stacks. Forgetting the second
pop is the classic bug: the stacks drift apart and
getMinstarts lying. - Line 19 (JS) / 16 (Py):
topreads the last item ofstack. - Line 23 (JS) / 19 (Py):
getMinreads the last item ofmins. One step.
Calls: push(5), push(2), push(8), getMin(), pop(), pop(), getMin().
Stacks are written bottom → top.
| call | stack after | mins after | returns |
|---|---|---|---|
| push(5) | [5] | [5] | null |
| push(2) | [5, 2] | [5, 2] | null |
| push(8) | [5, 2, 8] | [5, 2, 2] | null |
| getMin() | [5, 2, 8] | [5, 2, 2] | 2 |
| pop() | [5, 2] | [5, 2] | null |
| pop() | [5] | [5] | null |
| getMin() | [5] | [5] | 5 |
Look at the push(8) row: 8 is not a new minimum, so mins gets another 2.
That copy is what keeps the two stacks the same height, and it’s why the last
row can answer 5 instantly after the 2 is popped.
Brute force (scan on getMin)
Time
O(1) push/pop/top, O(n) getMin
getMin looks at every item on the stack, every time.
Space
O(n)
One stack holding up to n values.
Two stacks
Time
O(1) for every method
Each method does a fixed number of pushes, pops or reads, however tall the stack is.
Space
O(n)
Two stacks of n items each: 2n, which still grows in a straight line with n.
What to say out loud, in this order:
- Clarify the API and the O(1) requirement for every method, including
getMin. - Mention the naive version: “scan on getMin is O(n), so it fails the requirement.”
- Spot the key fact: “a stack only changes at the top, so the minimum at each height never changes after it’s pushed.”
- Propose the auxiliary
minsstack, and say that both stacks are always the same height. - Walk through a pop of the current minimum to show the old minimum comes back for free.
Likely follow-up questions:
- “Max stack?” Same idea with
Math.max/max. - “Can you use less memory?” Push to
minsonly whenval <= mins.top(note the<=, for duplicates). - “Min of a queue?” Harder: a queue changes at both ends. Two stacks can simulate a queue, each with its own min stack.
Related problems:
- Valid Parentheses (this week): the stack basics.
- Daily Temperatures (this week): another stack that keeps extra order information to answer questions fast.
- The week 3 overview has the template.