Augmented Entries (Store a Running Min/Max/Count With Each Item)
Min Stack (LC 155)(opens leetcode.com)
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.
-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.Min-Stack Trick
push / pop stream ➔ each entry stores the running min with it ➔ O(1) queryO(1) per call while items are pushed and popped.| 1 | class MinStack: |
| 2 | """Min Stack: each entry carries the minimum of itself and every entry below it. |
| 3 | Time: O(1) per call | Space: O(N) |
| 4 | """ |
| 5 | |
| 6 | def __init__(self) -> None: |
| 7 | # self.stack: one (val, current_min) pair per pushed value; current_min is the minimum of val |
| 8 | # and every entry below it, so the top entry always knows the whole stack's minimum. |
| 9 | self.stack: list[tuple[int, int]] = [] |
| 10 | |
| 11 | def push(self, val: int) -> None: |
| 12 | # 1. Compute This Entry's Running Minimum: |
| 13 | # Extend the minimum carried by the entry below with val, or start fresh when the stack is empty. |
| 14 | if self.stack: |
| 15 | current_min = min(val, self.stack[-1][1]) |
| 16 | else: |
| 17 | current_min = val |
| 18 | |
| 19 | # 2. Store The Value Together With Its Running Minimum: |
| 20 | # Pairing them means nothing below this entry has to change while it stays on the stack. |
| 21 | self.stack.append((val, current_min)) |
| 22 | |
| 23 | def pop(self) -> None: |
| 24 | self.stack.pop() # The new top already carries the minimum of what is left |
| 25 | |
| 26 | def top(self) -> int: |
| 27 | return self.stack[-1][0] |
| 28 | |
| 29 | def getMin(self) -> int: |
| 30 | return self.stack[-1][1] # Read it off the top entry: no search |
(val, current_min) in self.stack holds the minimum of its own val and every value below it, so self.stack[-1][1] is always the minimum of the whole stack.A stack only changes at its top, so store with each entry the answer for itself and everything below it: push appends (val, current_min) with current_min = min(val, self.stack[-1][1]), and getMin just reads self.stack[-1][1]. While an entry sits on the stack nothing below it can change, so its current_min stays true until the entry itself is popped; pop removes exactly one entry, and the new top already carries the minimum of what is left, so nothing is ever recomputed. The same move carries any value you can build from the entry below: a maximum, a count or a pending increment. The trap is keeping one self.min for the whole stack: it is right after every push, but when pop removes the smallest value it can't know the next smallest without a scan.
See it run
Min Stack, step by step
stack emptyreturned none
The two top rows are the calls and their arguments. The rows val and min are the stack: each column is one entry, with the bottom entry in column 0. val is the stored value and min is its current_min.
callthe call that is running nowwritea value or a current_min that was just stored in a new entryreada stored value or current_min that the call readspoppedthe entry that pop removes
Start: self.stack is empty. The calls are listed in the two top rows and run from left to right.
Gotcha 1 of 4
- The trap
Gotcha 1: Keeping one
self.minfor the whole stackMistakedef getMin(self) -> int: return self.minFixdef getMin(self) -> int: return self.stack[-1][1]What happens: One variable
self.minis correct after everypush. Whenpopremoves the smallest value,self.minstill holds it. Finding the next smallest value would need a scan of the whole stack. Each entry's owncurrent_minalready holds that value.Example: push(-2), push(0), push(-3), pop(), getMin()Mistake: returns -3Fix: returns -2
- Each item waits for a later, larger item, as in Daily Temperatures (LC 739): an entry's answer is decided when a newcomer pops it, not by a value stored when it was pushed, so keep a monotonic stack of waiting indices. See Next Greater Element
Deep Dive
Why each entry can carry its own minimum
A stack changes only at its top. While an entry sits on self.stack, the entries below it cannot change. So the minimum of that entry and everything below it stays true until the entry itself is popped.
push stores the pair (val, current_min). It computes current_min = min(val, self.stack[-1][1]), which extends the minimum of the entry below with the new value. getMin reads self.stack[-1][1]. pop removes one entry, and the new top already holds the minimum of what is left. Nothing is ever recomputed.
The board replays the example of Min Stack (LC 155). The calls are push(-2), push(0), push(-3), getMin(), pop(), top() and getMin(). The entries are (-2, -2), (0, -2) and (-3, -3). The first getMin() returns -3. After pop(), the top is (0, -2), so top() returns 0 and the last getMin() returns -2.
The last getMin() is marked as the trap on the board. A single variable self.min would still hold -3 there, because -3 was the smallest value pushed. It would need a scan of the stack to find -2.
The three mistakes inside push, top and getMin
Compare with the minimum of the entry below, self.stack[-1][1], and not with its value, self.stack[-1][0]. After push(1), push(5) and push(3), the value below 3 is 5. Comparing with 5 gives current_min = 3. Comparing with the stored minimum gives 1, which is correct.
The first push has no entry below. self.stack[-1] on an empty list raises an IndexError. The first entry is its own minimum, so current_min = val.
top returns index 0 of the top pair, and getMin returns index 1. After push(-2) and push(0), top() must return 0. Returning index 1 gives -2.
Other values an entry can carry
The same move works for any value that can be built from the entry below. For a maximum, store max(val, below_max). For a count, store the count of the entry below plus one if val matches a condition.
Max Stack (LC 716) uses the pair for peekMax in O(1). Its popMax removes an item from the middle of the stack, and one pair per entry cannot do that, so that call needs a different structure.
Design a Stack With Increment Operation (LC 1381) carries a pending increment. An increment of the bottom k items is recorded on one entry, and pop adds it to the value it returns and passes it to the entry below. Each call stays O(1).
A second way to get the same result is a separate stack of minimums. It pushes to the second stack when val is less than or equal to the current minimum. It saves space when there are many repeated large values. The pair version is easier to get right.
The cost
Every call does a constant amount of work. push makes one min call, and pop, top and getMin read or remove one entry. So each call is O(1).
The stack holds N entries after N pushes, and each entry has two numbers. The space is O(N), and it is about twice the size of a stack of plain values.
Example: after 1000 pushes, self.stack holds 1000 pairs, and getMin() reads one of them. A scan for the minimum would read all 1000.
60-Second Pitch
"A stack changes only at its top. So I store with each entry the answer for itself and everything below it. push appends (val, current_min) with current_min = min(val, self.stack[-1][1]). While an entry is on the stack, nothing below it changes, so its current_min stays true. getMin reads the top entry, and pop removes one entry. The new top already holds the minimum of what is left. Every call is O(1), and the space is O(N), with two numbers per entry. The same pair works for a maximum or a count."
Common Questions
- Why not keep one variable
self.min? It is correct after every
push. Whenpopremoves the smallest value,self.minstill holds that value. Finding the next smallest value needs a scan of the whole stack. Thecurrent_minstored with each entry avoids the scan.- Why is the stored
current_minalways correct? An entry is added only at the top, and it is removed only from the top. While it is on the stack, the entries below it cannot change. So the minimum of the entry and everything below it stays the same until the entry is popped.
- What are the time and space complexity?
Every call is
O(1). The space isO(N)forNentries, with two numbers per entry.- Can the same idea track a maximum or a count?
Yes. Store the maximum of
valand the maximum below, or a count built from the count below. This works for any value that depends only on the entry and the entries below it. It does not work for removing an item from the middle, as inpopMaxof Max Stack (LC 716).- How can you save space?
Keep a second stack that holds a value only when it is less than or equal to the current minimum. Pop from it when the same value leaves the main stack. This uses less space when most values are large, but the pair version has less code to get wrong.
SWE Reasoning
Spot it
- A stack or a queue must answer a question about all of its contents, such as the minimum, the maximum or a count.
- The answer must be
O(1)per call while items are pushed and popped. - The answer for an entry depends only on the entry itself and the entries below it.
- A scan of the whole structure on each query would be too slow.
- The question would be easy to answer if the structure could not lose items. Only
popmakes it hard.
The invariant, step by step
self.stackstarts empty. Each entry is a pair(val, current_min).pushcomputescurrent_minfrom the entry below. If the stack is empty,current_min = val. Otherwisecurrent_min = min(val, self.stack[-1][1]).- The pair is appended, so every entry holds the minimum of its own
valand every value below it. - Entries below cannot change while an entry sits above them, so the stored
current_minstays true. popremoves the top pair. The new top still holds the minimum of what is left.getMinreturnsself.stack[-1][1], andtopreturnsself.stack[-1][0]. Both areO(1).
Traps
- One
self.minfor the whole stack. It is right after everypush, but after apopof the smallest value it is out of date. Forpush(-2),push(0),push(-3),pop(),getMin(), it returns -3 and not -2. - Comparing with the value below. Use
self.stack[-1][1], the minimum below, and notself.stack[-1][0]. - The first push. An empty
self.stackhas noself.stack[-1]. Handle it withcurrent_min = val. - Wrong index in
top. The value is at index 0. Index 1 is the minimum. - Recomputing on
pop. If you scan the stack after apop, the call isO(N). The new top already has the answer.
Practice
Augmented Entries (Store a Running Min/Max/Count With Each Item)
Min Stack (LC 155)(opens leetcode.com)
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.
-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.Min-Stack Trick
push / pop stream ➔ each entry stores the running min with it ➔ O(1) queryO(1) per call while items are pushed and popped.| 1 | class MinStack: |
| 2 | """Min Stack: each entry carries the minimum of itself and every entry below it. |
| 3 | Time: O(1) per call | Space: O(N) |
| 4 | """ |
| 5 | |
| 6 | def __init__(self) -> None: |
| 7 | # self.stack: one (val, current_min) pair per pushed value; current_min is the minimum of val |
| 8 | # and every entry below it, so the top entry always knows the whole stack's minimum. |
| 9 | self.stack: list[tuple[int, int]] = [] |
| 10 | |
| 11 | def push(self, val: int) -> None: |
| 12 | # 1. Compute This Entry's Running Minimum: |
| 13 | # Extend the minimum carried by the entry below with val, or start fresh when the stack is empty. |
| 14 | if self.stack: |
| 15 | current_min = min(val, self.stack[-1][1]) |
| 16 | else: |
| 17 | current_min = val |
| 18 | |
| 19 | # 2. Store The Value Together With Its Running Minimum: |
| 20 | # Pairing them means nothing below this entry has to change while it stays on the stack. |
| 21 | self.stack.append((val, current_min)) |
| 22 | |
| 23 | def pop(self) -> None: |
| 24 | self.stack.pop() # The new top already carries the minimum of what is left |
| 25 | |
| 26 | def top(self) -> int: |
| 27 | return self.stack[-1][0] |
| 28 | |
| 29 | def getMin(self) -> int: |
| 30 | return self.stack[-1][1] # Read it off the top entry: no search |
(val, current_min) in self.stack holds the minimum of its own val and every value below it, so self.stack[-1][1] is always the minimum of the whole stack.A stack only changes at its top, so store with each entry the answer for itself and everything below it: push appends (val, current_min) with current_min = min(val, self.stack[-1][1]), and getMin just reads self.stack[-1][1]. While an entry sits on the stack nothing below it can change, so its current_min stays true until the entry itself is popped; pop removes exactly one entry, and the new top already carries the minimum of what is left, so nothing is ever recomputed. The same move carries any value you can build from the entry below: a maximum, a count or a pending increment. The trap is keeping one self.min for the whole stack: it is right after every push, but when pop removes the smallest value it can't know the next smallest without a scan.
See it run
Min Stack, step by step
stack emptyreturned none
The two top rows are the calls and their arguments. The rows val and min are the stack: each column is one entry, with the bottom entry in column 0. val is the stored value and min is its current_min.
callthe call that is running nowwritea value or a current_min that was just stored in a new entryreada stored value or current_min that the call readspoppedthe entry that pop removes
Start: self.stack is empty. The calls are listed in the two top rows and run from left to right.
Gotcha 1 of 4
- The trap
Gotcha 1: Keeping one
self.minfor the whole stackMistakedef getMin(self) -> int: return self.minFixdef getMin(self) -> int: return self.stack[-1][1]What happens: One variable
self.minis correct after everypush. Whenpopremoves the smallest value,self.minstill holds it. Finding the next smallest value would need a scan of the whole stack. Each entry's owncurrent_minalready holds that value.Example: push(-2), push(0), push(-3), pop(), getMin()Mistake: returns -3Fix: returns -2
- Each item waits for a later, larger item, as in Daily Temperatures (LC 739): an entry's answer is decided when a newcomer pops it, not by a value stored when it was pushed, so keep a monotonic stack of waiting indices. See Next Greater Element
Deep Dive
Why each entry can carry its own minimum
A stack changes only at its top. While an entry sits on self.stack, the entries below it cannot change. So the minimum of that entry and everything below it stays true until the entry itself is popped.
push stores the pair (val, current_min). It computes current_min = min(val, self.stack[-1][1]), which extends the minimum of the entry below with the new value. getMin reads self.stack[-1][1]. pop removes one entry, and the new top already holds the minimum of what is left. Nothing is ever recomputed.
The board replays the example of Min Stack (LC 155). The calls are push(-2), push(0), push(-3), getMin(), pop(), top() and getMin(). The entries are (-2, -2), (0, -2) and (-3, -3). The first getMin() returns -3. After pop(), the top is (0, -2), so top() returns 0 and the last getMin() returns -2.
The last getMin() is marked as the trap on the board. A single variable self.min would still hold -3 there, because -3 was the smallest value pushed. It would need a scan of the stack to find -2.
The three mistakes inside push, top and getMin
Compare with the minimum of the entry below, self.stack[-1][1], and not with its value, self.stack[-1][0]. After push(1), push(5) and push(3), the value below 3 is 5. Comparing with 5 gives current_min = 3. Comparing with the stored minimum gives 1, which is correct.
The first push has no entry below. self.stack[-1] on an empty list raises an IndexError. The first entry is its own minimum, so current_min = val.
top returns index 0 of the top pair, and getMin returns index 1. After push(-2) and push(0), top() must return 0. Returning index 1 gives -2.
Other values an entry can carry
The same move works for any value that can be built from the entry below. For a maximum, store max(val, below_max). For a count, store the count of the entry below plus one if val matches a condition.
Max Stack (LC 716) uses the pair for peekMax in O(1). Its popMax removes an item from the middle of the stack, and one pair per entry cannot do that, so that call needs a different structure.
Design a Stack With Increment Operation (LC 1381) carries a pending increment. An increment of the bottom k items is recorded on one entry, and pop adds it to the value it returns and passes it to the entry below. Each call stays O(1).
A second way to get the same result is a separate stack of minimums. It pushes to the second stack when val is less than or equal to the current minimum. It saves space when there are many repeated large values. The pair version is easier to get right.
The cost
Every call does a constant amount of work. push makes one min call, and pop, top and getMin read or remove one entry. So each call is O(1).
The stack holds N entries after N pushes, and each entry has two numbers. The space is O(N), and it is about twice the size of a stack of plain values.
Example: after 1000 pushes, self.stack holds 1000 pairs, and getMin() reads one of them. A scan for the minimum would read all 1000.
60-Second Pitch
"A stack changes only at its top. So I store with each entry the answer for itself and everything below it. push appends (val, current_min) with current_min = min(val, self.stack[-1][1]). While an entry is on the stack, nothing below it changes, so its current_min stays true. getMin reads the top entry, and pop removes one entry. The new top already holds the minimum of what is left. Every call is O(1), and the space is O(N), with two numbers per entry. The same pair works for a maximum or a count."
Common Questions
- Why not keep one variable
self.min? It is correct after every
push. Whenpopremoves the smallest value,self.minstill holds that value. Finding the next smallest value needs a scan of the whole stack. Thecurrent_minstored with each entry avoids the scan.- Why is the stored
current_minalways correct? An entry is added only at the top, and it is removed only from the top. While it is on the stack, the entries below it cannot change. So the minimum of the entry and everything below it stays the same until the entry is popped.
- What are the time and space complexity?
Every call is
O(1). The space isO(N)forNentries, with two numbers per entry.- Can the same idea track a maximum or a count?
Yes. Store the maximum of
valand the maximum below, or a count built from the count below. This works for any value that depends only on the entry and the entries below it. It does not work for removing an item from the middle, as inpopMaxof Max Stack (LC 716).- How can you save space?
Keep a second stack that holds a value only when it is less than or equal to the current minimum. Pop from it when the same value leaves the main stack. This uses less space when most values are large, but the pair version has less code to get wrong.
SWE Reasoning
Spot it
- A stack or a queue must answer a question about all of its contents, such as the minimum, the maximum or a count.
- The answer must be
O(1)per call while items are pushed and popped. - The answer for an entry depends only on the entry itself and the entries below it.
- A scan of the whole structure on each query would be too slow.
- The question would be easy to answer if the structure could not lose items. Only
popmakes it hard.
The invariant, step by step
self.stackstarts empty. Each entry is a pair(val, current_min).pushcomputescurrent_minfrom the entry below. If the stack is empty,current_min = val. Otherwisecurrent_min = min(val, self.stack[-1][1]).- The pair is appended, so every entry holds the minimum of its own
valand every value below it. - Entries below cannot change while an entry sits above them, so the stored
current_minstays true. popremoves the top pair. The new top still holds the minimum of what is left.getMinreturnsself.stack[-1][1], andtopreturnsself.stack[-1][0]. Both areO(1).
Traps
- One
self.minfor the whole stack. It is right after everypush, but after apopof the smallest value it is out of date. Forpush(-2),push(0),push(-3),pop(),getMin(), it returns -3 and not -2. - Comparing with the value below. Use
self.stack[-1][1], the minimum below, and notself.stack[-1][0]. - The first push. An empty
self.stackhas noself.stack[-1]. Handle it withcurrent_min = val. - Wrong index in
top. The value is at index 0. Index 1 is the minimum. - Recomputing on
pop. If you scan the stack after apop, the call isO(N). The new top already has the answer.