Min Stack (LeetCode 155)
Build a stack class, MinStack, that behaves like any last-in, first-out stack but can also report its smallest value at any moment. Each of its operations has to run in O(1) time.
MinStack()creates an empty stack.void push(int val)putsvalon top.void pop()throws away the value on top.int top()returns the value on top and leaves it in place.int getMin()returns the smallest value among everything currently on the stack.
Worked Examples
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]][null,null,null,null,-3,null,0,-2]-2, 0 and -3 are pushed, the smallest value is -3. Popping removes -3, so 0 is on top again and the smallest value goes back to -2.⚖️Formal Constraints & Bounds
-231 <= val <= 231 - 1pop,topandgetMinare only called when the stack is not empty.At most
3 * 104calls are made topush,pop,topandgetMinaltogether.
Core Insight
A stack only changes at its top, so nothing below an entry changes while the entry is there: store with each entry the minimum from the bottom up to it, and the top entry holds the answer before and after every pop.
Real-World Scenario & Production Applications
An undo history, a call stack in a profiler or a parser's stack often has to report the lowest (or highest, or total) value among everything still on it, right after every push and pop. Rescanning the stack after each change costs time proportional to its size; storing the answer with each entry makes it one read.
Step-by-Step Execution Trace Table
Example 1 (the trap case: the minimum is popped):
| Call | self.stack after the call (bottom to top) | Returns | What happened |
|---|---|---|---|
MinStack() | [] | null | An empty stack |
push(-2) | [(-2, -2)] | null | First entry: current_min = val = -2 |
push(0) | [(-2, -2), (0, -2)] | null | min(0, -2) = -2: the minimum carried below wins |
push(-3) | [(-2, -2), (0, -2), (-3, -3)] | null | min(-3, -2) = -3: a new minimum |
getMin() | unchanged | -3 | Read self.stack[-1][1] |
pop() | [(-2, -2), (0, -2)] | null | The new top already carries -2: nothing to recompute |
top() | unchanged | 0 | Read self.stack[-1][0] |
getMin() | unchanged | -2 | One self.min variable would still say -3 here |
| 1 | A stack only changes at its top, so what is below an entry never changes while the entry is there: store the answer for the bottom-up part with the entry, as a pair `(val, current_min)`. |
| 2 | Keep this true: each entry's `current_min` is the minimum of its own `val` and every value below it, so `self.stack[-1][1]` answers `getMin`. |
| 3 | `push`: `current_min = min(val, self.stack[-1][1])` when the stack has entries, else `val`, then append the pair; `pop` removes the top pair; `top` reads `self.stack[-1][0]`. |
| 4 | The trap: don't keep one `self.min` for the whole stack. After the smallest value is popped it can't give you the next smallest; the new top's `self.stack[-1][1]` already does. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A plain stack answers top() at once but has to scan everything to find its minimum. One running variable, self.min, fixes push but breaks pop: when the smallest value leaves, the variable can't know the next smallest. The Min-Stack Trick uses the one fact that makes a stack special: it only ever changes at its top. While an entry sits on the stack, nothing below it changes, so the minimum of "this entry and everything below it" stays true until the entry itself is popped. Compute that minimum once, at push time, and store it in the entry as (val, current_min). The top entry then always holds the minimum of the whole stack, and pop needs no repair.
🥞 The Analogy: A Pile of Plates With a Note on Each
You pile up plates of different sizes, and someone keeps asking for the size of the smallest plate in the pile. Each time you put a plate down, you stick a note on it: "the smallest plate from here down is size X", copying the number from the note below if that one is smaller. To answer, you read the note on the top plate. When you lift a plate off, the note on the plate now on top was written when that plate was the top, and nothing under it has changed since, so it is still right.
🔑 Why It Works
current_min is a running minimum from the bottom of the stack up to this entry, and it is stored with the entry, so every prefix of the stack keeps its own answer. Popping removes exactly one prefix, and the prefix below still has its answer on its own top entry. Compare val with the minimum carried below, self.stack[-1][1], not with the value below, self.stack[-1][0].
One running minimum for the whole stack: a single
self.minis right after everypushbut not after apopof the minimum: on LeetCode's example it still says-3after-3is popped. Storecurrent_minin each entry, and the new top already knows-2.Comparing with the value below instead of the minimum below:
min(val, self.stack[-1][0])looks at one neighbour only; afterpush(1),push(5),push(3)it stores3as the minimum instead of1. Useself.stack[-1][1].Reading
self.stack[-1]on the first push: an empty stack has no top, so the first entry'scurrent_minisvalitself (if self.stack: ... else: current_min = val).Two stacks with a strict
<: in the two-stack version, push onto the minimum stack whenval <= min_stack[-1]. With<, pushing0,1,0and popping once throws away the only record of0while a0is still on the stack.Scanning on
getMin:min(v for v, _ in self.stack)is correct butO(N)per call, about2 * 108steps at these limits; the carried minimum makes it one read.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Retrieve the minimum element in constant time" on a structure that also pushes and pops: a question about the stack's whole contents (its minimum), answered in O(1) per call while values come and go. A stack only ever changes at its top, which is the signal for the Min-Stack Trick: store the answer with each entry.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Decision rule: push stores current_min = min(val, self.stack[-1][1]) (or val on an empty stack); pop only removes the top pair; getMin reads self.stack[-1][1].
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use the Min-Stack Trick: store extra state with each entry. A stack only changes at its top, so nothing below an entry changes while that entry is on the stack. That lets me store, with each value, the minimum of itself and everything below it, as a pair: val and current min. On push, current min is the smaller of val and the minimum carried by the entry below, or just val when the stack is empty. getMin reads the second field of the top pair, and pop removes the top pair: the new top already carries the minimum of what is left, so nothing is recomputed. The trap is one running min variable for the whole stack: after the smallest value is popped, it can't tell you the next smallest without a scan. Every call is
O(1)time, and the pairs takeO(N)space.
Complexity & Mathematical Proof
O(1) per call
Look at each method. push does one test (if self.stack), at most one min of two numbers and one append; pop removes the last list item; top and getMin each read one field of self.stack[-1]. No method loops over the stack, so every call is O(1) (appending to and popping from the end of a Python list are amortized O(1)), and a run of Q calls costs O(Q).
O(N)
self.stack holds one (val, current_min) pair for each of the N values on the stack: 2N numbers, so O(N) space. Carrying the minimum doubles the memory of a plain stack; that is the price of an O(1) getMin.
T(Q) = Q · O(1) = O(Q) for Q calls
Derivation Progression
O(1)
One test if self.stack, at most one min of two numbers, one append at the end of the list.
O(1)
self.stack.pop() removes the last pair; nothing is recomputed, because the new top already carries its minimum.
O(1)
Each reads one field of self.stack[-1]: no loop over the stack.
O(Q)
Constant work per call over Q calls.
Variable Definitions
Number of values on the stack, len(self.stack)
Number of calls to push, pop, top and getMin (at most 3 * 104)
Memory Architecture & Bounds
O(1) No recursion
O(N): one (val, current_min) pair per value, twice a plain stack
O(1) per call: one integer or nothing
Boundary Best / Worst Cases
per call
per call
amortized per call (a Python list occasionally grows its buffer on append)
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "retrieve the minimum element in constant time", "push, pop, top". A question about the whole stack (its minimum) that must be answered in while values come and go at the top: Min-Stack Trick, store the answer with each entry.
Up to calls and values in . Scanning the stack on every getMin costs up to steps per call, about in total; one (val, current_min) pair per entry makes every call for memory, twice a plain stack.
If several threads share the stack, push and pop each pair as one unit: two separate stacks (values and minimums) updated in two steps can drift apart. The carried minimum has the same type as the value, so the edge needs no special case.
Core Algorithmic State Invariants
- Repeated Minimums Are Safe
Pushing -2 twice stores current_min = -2 in both pairs, so popping one still leaves -2 as the minimum. The pair form never needs the <= care that the two-stack version does.
- Trading Memory for Simplicity
The pairs cost one extra number per entry. A second stack that records a minimum only when it changes saves memory on long runs of larger values, at the price of the <= rule and two structures to keep in step.
Min Stack (LeetCode 155)
Build a stack class, MinStack, that behaves like any last-in, first-out stack but can also report its smallest value at any moment. Each of its operations has to run in O(1) time.
MinStack()creates an empty stack.void push(int val)putsvalon top.void pop()throws away the value on top.int top()returns the value on top and leaves it in place.int getMin()returns the smallest value among everything currently on the stack.
Worked Examples
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]][null,null,null,null,-3,null,0,-2]-2, 0 and -3 are pushed, the smallest value is -3. Popping removes -3, so 0 is on top again and the smallest value goes back to -2.⚖️Formal Constraints & Bounds
-231 <= val <= 231 - 1pop,topandgetMinare only called when the stack is not empty.At most
3 * 104calls are made topush,pop,topandgetMinaltogether.
Core Insight
A stack only changes at its top, so nothing below an entry changes while the entry is there: store with each entry the minimum from the bottom up to it, and the top entry holds the answer before and after every pop.
Real-World Scenario & Production Applications
An undo history, a call stack in a profiler or a parser's stack often has to report the lowest (or highest, or total) value among everything still on it, right after every push and pop. Rescanning the stack after each change costs time proportional to its size; storing the answer with each entry makes it one read.
Step-by-Step Execution Trace Table
Example 1 (the trap case: the minimum is popped):
| Call | self.stack after the call (bottom to top) | Returns | What happened |
|---|---|---|---|
MinStack() | [] | null | An empty stack |
push(-2) | [(-2, -2)] | null | First entry: current_min = val = -2 |
push(0) | [(-2, -2), (0, -2)] | null | min(0, -2) = -2: the minimum carried below wins |
push(-3) | [(-2, -2), (0, -2), (-3, -3)] | null | min(-3, -2) = -3: a new minimum |
getMin() | unchanged | -3 | Read self.stack[-1][1] |
pop() | [(-2, -2), (0, -2)] | null | The new top already carries -2: nothing to recompute |
top() | unchanged | 0 | Read self.stack[-1][0] |
getMin() | unchanged | -2 | One self.min variable would still say -3 here |
| 1 | A stack only changes at its top, so what is below an entry never changes while the entry is there: store the answer for the bottom-up part with the entry, as a pair `(val, current_min)`. |
| 2 | Keep this true: each entry's `current_min` is the minimum of its own `val` and every value below it, so `self.stack[-1][1]` answers `getMin`. |
| 3 | `push`: `current_min = min(val, self.stack[-1][1])` when the stack has entries, else `val`, then append the pair; `pop` removes the top pair; `top` reads `self.stack[-1][0]`. |
| 4 | The trap: don't keep one `self.min` for the whole stack. After the smallest value is popped it can't give you the next smallest; the new top's `self.stack[-1][1]` already does. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A plain stack answers top() at once but has to scan everything to find its minimum. One running variable, self.min, fixes push but breaks pop: when the smallest value leaves, the variable can't know the next smallest. The Min-Stack Trick uses the one fact that makes a stack special: it only ever changes at its top. While an entry sits on the stack, nothing below it changes, so the minimum of "this entry and everything below it" stays true until the entry itself is popped. Compute that minimum once, at push time, and store it in the entry as (val, current_min). The top entry then always holds the minimum of the whole stack, and pop needs no repair.
🥞 The Analogy: A Pile of Plates With a Note on Each
You pile up plates of different sizes, and someone keeps asking for the size of the smallest plate in the pile. Each time you put a plate down, you stick a note on it: "the smallest plate from here down is size X", copying the number from the note below if that one is smaller. To answer, you read the note on the top plate. When you lift a plate off, the note on the plate now on top was written when that plate was the top, and nothing under it has changed since, so it is still right.
🔑 Why It Works
current_min is a running minimum from the bottom of the stack up to this entry, and it is stored with the entry, so every prefix of the stack keeps its own answer. Popping removes exactly one prefix, and the prefix below still has its answer on its own top entry. Compare val with the minimum carried below, self.stack[-1][1], not with the value below, self.stack[-1][0].
One running minimum for the whole stack: a single
self.minis right after everypushbut not after apopof the minimum: on LeetCode's example it still says-3after-3is popped. Storecurrent_minin each entry, and the new top already knows-2.Comparing with the value below instead of the minimum below:
min(val, self.stack[-1][0])looks at one neighbour only; afterpush(1),push(5),push(3)it stores3as the minimum instead of1. Useself.stack[-1][1].Reading
self.stack[-1]on the first push: an empty stack has no top, so the first entry'scurrent_minisvalitself (if self.stack: ... else: current_min = val).Two stacks with a strict
<: in the two-stack version, push onto the minimum stack whenval <= min_stack[-1]. With<, pushing0,1,0and popping once throws away the only record of0while a0is still on the stack.Scanning on
getMin:min(v for v, _ in self.stack)is correct butO(N)per call, about2 * 108steps at these limits; the carried minimum makes it one read.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Retrieve the minimum element in constant time" on a structure that also pushes and pops: a question about the stack's whole contents (its minimum), answered in O(1) per call while values come and go. A stack only ever changes at its top, which is the signal for the Min-Stack Trick: store the answer with each entry.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Decision rule: push stores current_min = min(val, self.stack[-1][1]) (or val on an empty stack); pop only removes the top pair; getMin reads self.stack[-1][1].
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use the Min-Stack Trick: store extra state with each entry. A stack only changes at its top, so nothing below an entry changes while that entry is on the stack. That lets me store, with each value, the minimum of itself and everything below it, as a pair: val and current min. On push, current min is the smaller of val and the minimum carried by the entry below, or just val when the stack is empty. getMin reads the second field of the top pair, and pop removes the top pair: the new top already carries the minimum of what is left, so nothing is recomputed. The trap is one running min variable for the whole stack: after the smallest value is popped, it can't tell you the next smallest without a scan. Every call is
O(1)time, and the pairs takeO(N)space.
Complexity & Mathematical Proof
O(1) per call
Look at each method. push does one test (if self.stack), at most one min of two numbers and one append; pop removes the last list item; top and getMin each read one field of self.stack[-1]. No method loops over the stack, so every call is O(1) (appending to and popping from the end of a Python list are amortized O(1)), and a run of Q calls costs O(Q).
O(N)
self.stack holds one (val, current_min) pair for each of the N values on the stack: 2N numbers, so O(N) space. Carrying the minimum doubles the memory of a plain stack; that is the price of an O(1) getMin.
T(Q) = Q · O(1) = O(Q) for Q calls
Derivation Progression
O(1)
One test if self.stack, at most one min of two numbers, one append at the end of the list.
O(1)
self.stack.pop() removes the last pair; nothing is recomputed, because the new top already carries its minimum.
O(1)
Each reads one field of self.stack[-1]: no loop over the stack.
O(Q)
Constant work per call over Q calls.
Variable Definitions
Number of values on the stack, len(self.stack)
Number of calls to push, pop, top and getMin (at most 3 * 104)
Memory Architecture & Bounds
O(1) No recursion
O(N): one (val, current_min) pair per value, twice a plain stack
O(1) per call: one integer or nothing
Boundary Best / Worst Cases
per call
per call
amortized per call (a Python list occasionally grows its buffer on append)
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "retrieve the minimum element in constant time", "push, pop, top". A question about the whole stack (its minimum) that must be answered in while values come and go at the top: Min-Stack Trick, store the answer with each entry.
Up to calls and values in . Scanning the stack on every getMin costs up to steps per call, about in total; one (val, current_min) pair per entry makes every call for memory, twice a plain stack.
If several threads share the stack, push and pop each pair as one unit: two separate stacks (values and minimums) updated in two steps can drift apart. The carried minimum has the same type as the value, so the edge needs no special case.
Core Algorithmic State Invariants
- Repeated Minimums Are Safe
Pushing -2 twice stores current_min = -2 in both pairs, so popping one still leaves -2 as the minimum. The pair form never needs the <= care that the two-stack version does.
- Trading Memory for Simplicity
The pairs cost one extra number per entry. A second stack that records a minimum only when it changes saves memory on long runs of larger values, at the price of the <= rule and two structures to keep in step.