Monotonic Stack (Next Greater Element)
You're given an array of integers temperatures, one reading per day. Build an output array answer where answer[i] counts how many days you'd have to wait, looking only forward from day i, until a strictly warmer day shows up. When no such day ever comes later in the array, answer[i] stays 0.
75 on day 2, the next warmer day is the 76 on day 6, 4 days later. Nothing after the last 76 or 73 is warmer, so they get 0.Next Greater Element
stream of values ➔ stack of strictly decreasing indices ➔ pop on violation| 1 | from typing import Callable, List, Sequence, TypeVar |
| 2 | |
| 3 | Item = TypeVar("Item") |
| 4 | |
| 5 | |
| 6 | def next_greater(values: Sequence[Item], pops: Callable[[Item, Item], bool]) -> List[int]: |
| 7 | """Next Greater Element: for each index, the first later index whose value answers it, or -1. |
| 8 | pops(top, value) is True when value answers the waiting value top, for example top < value. |
| 9 | Precondition: when value does not pop the top of the stack, it pops no index below the top either. |
| 10 | This holds for the comparisons <, <=, > and >=. |
| 11 | 132 Pattern and Online Stock Span (a class that answers one value at a time) do not fit. |
| 12 | N = len(values). T = the cost of one pops call. |
| 13 | Time: O(N * T) | Space: O(N) |
| 14 | """ |
| 15 | n = len(values) |
| 16 | answer = [-1] * n # -1: no later value answers this index |
| 17 | stack: List[int] = [] # Holds INDICES of values still waiting for an answer, newest on top |
| 18 | |
| 19 | # 1. Visit Each Value Left To Right: |
| 20 | # Scanning once suffices because an index can only be answered by a later index, so by the time value is reached, every index that could answer it has already arrived. |
| 21 | for i, value in enumerate(values): |
| 22 | # 2. Resolve Every Waiting Index That `pops` Answers: |
| 23 | # While value answers the index on top of the stack, pop it and record i as its answer. The precondition guarantees that once value stops answering the top, it cannot answer anything buried below it either, so the while loop can stop there. |
| 24 | while stack and pops(values[stack[-1]], value): |
| 25 | prev_idx = stack.pop() # Answered by the current value |
| 26 | answer[prev_idx] = i |
| 27 | # 3. Push The Current Index As Still Waiting: |
| 28 | # Whatever remains unanswered after the pops above is now the newest index waiting for its own answer, so it goes on top. |
| 29 | stack.append(i) |
| 30 | |
| 31 | # 4. Return The Collected Answers: |
| 32 | # Any index left on the stack when the scan ends never found a later value that answers it, so it keeps its -1. |
| 33 | return answer |
stack never increase from bottom to top, and every index still in stack has not yet seen a warmer day.Keep stack as the indices still waiting for a warmer day, and when temp beats the temperature on top, i is that index's answer: pop it and write answer[prev_idx] = i - prev_idx. Every index below the top has a temperature at least as high as the top's, so if temp does not beat the top it cannot beat anything below it; each index is therefore answered by the first warmer day to its right, and never earlier. The trap is storing temperatures instead of indices: the answer is a distance written into its own slot of answer, so push i, not temp.
See it run
Monotonic Stack, step by step
stack []answer [0, 0, 0, 0, 0, 0, 0, 0]
The top row is the temperatures. The column number is the day index. The bottom row is the stack: the left cell is the bottom, each cell holds a day index, and a blank cell is an unused slot.
tempthe day being read nowpoppedthe day taken off the stack, whose answer is written nowtopthe top of the stack after a poppushedthe day index that was just pushed
Start: stack is empty and every slot of answer is 0.
Gotcha 1 of 4
- The trap
Gotcha 1: Pushing
tempinstead of the indexiMistakestack.append(temp)Fixstack.append(i)What happens: The answer is a distance,
i - prev_idx, written intoanswer[prev_idx]. Both need the day's index, and a temperature cannot give it. Withtemponstack, the loop readstemperatures[stack[-1]]with a temperature as the index. That index is past the end of the list, so Python raises an IndexError.Example: temperatures = [30, 40, 50, 60]Mistake: raises IndexErrorFix: returns [1, 1, 1, 0]
- Each answer is the largest value inside a window of fixed size that also drops old items from the front, as in Sliding Window Maximum (LC 239), not the first larger value to the right. See Monotonic Deque
- You need how far each bar reaches on both sides to size a rectangle, as in Largest Rectangle in Histogram (LC 84), not just its next larger value. See Histogram Stack
Deep Dive
Why one pass finds the first warmer day
A stack is last in, first out: the newest item is the only one you can read or remove. In Daily Temperatures (LC 739), stack holds the day indexes that have not found a warmer day yet. The newest waiting day is on top.
The temperatures at those indexes never increase from bottom to top. A new day i is pushed only after every colder day on top was popped. So the day that stays below it is at least as warm as temp.
This order lets the loop stop early. If temp is not above the top, then it is not above any index lower in stack, because those days are at least as warm as the top. The while loop can stop at the first top that stays.
An index is popped by the first later day that is warmer. Suppose a day j between prev_idx and i was warmer than prev_idx. Then j would have popped every colder index above it and then prev_idx itself, because the stack order does not let j skip over it. So no such j exists.
Example: temperatures = [73, 74, 75, 71, 69, 72, 76, 73] gives [1, 1, 4, 2, 1, 1, 0, 0]. Day 2 has temperature 75. It waits until day 6 has temperature 76, so answer[2] = 6 - 2 = 4.
One trace: pop and write the distance, then push the index
The board replays the example from the previous section. The top row is temperatures. The bottom row is stack, and each cell in it holds a day index.
Days 0 to 4 build the stack. Day 1 (74) pops day 0 and writes answer[0] = 1. Day 2 (75) pops day 1 and writes answer[1] = 1. Then days 3 and 4 are pushed, because 71 and 69 are not above the top. Now stack is [2, 3, 4].
Day 5 has temperature 72. It pops day 4 (69) and writes answer[4] = 1. It pops day 3 (71) and writes answer[3] = 2. It stops at day 2 (75), because 72 is not above 75. Then stack is [2, 5].
Day 6 has temperature 76. It pops day 5 and writes answer[5] = 1. It pops day 2 and writes answer[2] = 4. Day 7 (73) pops nothing. Days 6 and 7 stay on stack, so their answers stay 0.
The trap: push the index, and pop only on a strictly warmer day
Push i, not temp. The answer is a distance written into its own slot: answer[prev_idx] = i - prev_idx. Both parts need the day index, and a temperature cannot give it. With temperatures on stack, the line temperatures[stack[-1]] reads a temperature as an index. For [30, 40, 50, 60] that is past the end of the list, so Python raises IndexError.
Pop only when temperatures[stack[-1]] < temp. Daily Temperatures (LC 739) asks for a strictly warmer day. With <=, a day with the same temperature pops the earlier day. For temperatures = [70, 70, 71], the correct answer is [2, 1, 0]. With <=, day 0 is popped by day 1, and the result is [1, 1, 0].
Check the start value of answer. Daily Temperatures (LC 739) wants 0 for a day with no warmer day, so answer = [0] * n. Next Greater Element I (LC 496) wants -1 for that case. Indexes still on stack at the end keep the start value, because the loop never writes their slot.
The cost, and how to change the question
Every index is pushed once and popped at most once. The while loop looks nested, but the total number of pops over the whole run is at most N. So the time is O(N) when one pops call costs O(1), and the space is O(N). A list of falling temperatures such as [90, 80, 70, 60] keeps all N indexes on stack.
To find the next smaller value, reverse the comparison: pop while temperatures[stack[-1]] > temp. To find the previous greater value, read stack[-1] after the pops and before the push. That is the index of the nearest earlier day that is at least as warm.
The template needs one property: if temp does not pop the top, it pops nothing below it. The comparisons <, <=, > and >= all have it. 132 Pattern (LC 456) does not have it, so it needs more than this template. Online Stock Span (LC 901) uses the same stack, but it answers one value at a time inside a class.
Sliding Window Maximum (LC 239) looks similar, but it also removes old items from the front when they leave the window. That needs a deque, and it is a different card.
60-Second Pitch
"For each day I need the first later day that is warmer. I scan once from left to right and keep a stack of day indexes that are still waiting. When today's temperature is above the temperature on top, that top day has its answer: I pop it and write today's index minus its index. I repeat that until the top is at least as warm. Then I push today's index. The stack never increases in temperature from bottom to top, so once today fails to beat the top, it cannot beat anything below it. Each index is pushed once and popped at most once, so the time is O(N). The space is O(N) in the worst case. Days left on the stack at the end get 0."
Common Questions
- The code has a loop inside a loop. Why is it
O(N)and not O(N^2)? The inner
whileloop pops items, and each index is pushed exactly once, so it can be popped at most once. Over the whole run the inner loop runs at mostNtimes in total. The pushes costN, the pops cost at mostN, so the total isO(N).- Why does
stackhold indexes and not temperatures? The answer is a distance,
i - prev_idx, and it is written intoanswer[prev_idx]. Both need the index. A temperature can be read from the index withtemperatures[index], so nothing is lost by storing the index.- How do you find the previous greater element instead of the next one?
Use the same loop. After the
whileloop pops the colder days,stack[-1]is the nearest earlier day that is at least as warm. Read it before you pushi. Ifstackis empty, there is no such day.- Could you scan from right to left instead?
Yes. Keep a stack of candidates. For each day, pop the candidates that are not warmer, then the top is the answer. The cost is the same,
O(N). The left to right form writes each answer at the moment of the pop, which is the form the card uses.- How is this different from Sliding Window Maximum (LC 239)?
Here each element waits for the first larger value to its right, and nothing leaves the structure except by being answered. In Sliding Window Maximum (LC 239) a window of fixed size moves, so old indexes must also be removed from the front. That needs a deque.
SWE Reasoning
Spot it
- The question asks, for each element, for the next or previous element that is greater or smaller, or for the distance to it.
- The wording says "next warmer", "first taller", "until a larger value" or "how many days to wait".
- A pair of loops would compare each element with every later element, which is O(N^2) time. The input is large enough to rule that out.
- Each element is waiting for one event that depends only on a later value.
- The comparison is
<,<=,>or>=. All four satisfy the precondition of the template.
The invariant, step by step
stackstarts empty. It will hold day indexes that have not found a warmer day yet.- Day
iarrives with temperaturetemp. Every index onstackis a day beforei. - While
temperatures[stack[-1]] < temp, the top day has found its first warmer day. Pop it and writeanswer[prev_idx] = i - prev_idx. - The loop stops at a top that is at least as warm as
temp. Every index below that top is also at least as warm, so none of them can be answered bytemp. - Push
i. The temperatures onstackstill do not increase from bottom to top. - When the scan ends, the indexes still on
stacknever found a warmer day. They keep their start value inanswer.
Traps
stack.append(temp). The loop needs a day index to read the temperature and to compute the distance. Pushi.stack[-1] < temp.stack[-1]is a day number. Comparetemperatures[stack[-1]]withtemp.<=in the pop. A day with an equal temperature is not warmer. It must not pop the earlier day.answer = [-1] * nfor LC 739. Days with no warmer day must be 0. Next Greater Element I (LC 496) is the problem that wants -1.- Treating indexes left on the stack at the end as an error. They are not an error. They are the days with no answer.
Practice
Monotonic Stack (Next Greater Element)
You're given an array of integers temperatures, one reading per day. Build an output array answer where answer[i] counts how many days you'd have to wait, looking only forward from day i, until a strictly warmer day shows up. When no such day ever comes later in the array, answer[i] stays 0.
75 on day 2, the next warmer day is the 76 on day 6, 4 days later. Nothing after the last 76 or 73 is warmer, so they get 0.Next Greater Element
stream of values ➔ stack of strictly decreasing indices ➔ pop on violation| 1 | from typing import Callable, List, Sequence, TypeVar |
| 2 | |
| 3 | Item = TypeVar("Item") |
| 4 | |
| 5 | |
| 6 | def next_greater(values: Sequence[Item], pops: Callable[[Item, Item], bool]) -> List[int]: |
| 7 | """Next Greater Element: for each index, the first later index whose value answers it, or -1. |
| 8 | pops(top, value) is True when value answers the waiting value top, for example top < value. |
| 9 | Precondition: when value does not pop the top of the stack, it pops no index below the top either. |
| 10 | This holds for the comparisons <, <=, > and >=. |
| 11 | 132 Pattern and Online Stock Span (a class that answers one value at a time) do not fit. |
| 12 | N = len(values). T = the cost of one pops call. |
| 13 | Time: O(N * T) | Space: O(N) |
| 14 | """ |
| 15 | n = len(values) |
| 16 | answer = [-1] * n # -1: no later value answers this index |
| 17 | stack: List[int] = [] # Holds INDICES of values still waiting for an answer, newest on top |
| 18 | |
| 19 | # 1. Visit Each Value Left To Right: |
| 20 | # Scanning once suffices because an index can only be answered by a later index, so by the time value is reached, every index that could answer it has already arrived. |
| 21 | for i, value in enumerate(values): |
| 22 | # 2. Resolve Every Waiting Index That `pops` Answers: |
| 23 | # While value answers the index on top of the stack, pop it and record i as its answer. The precondition guarantees that once value stops answering the top, it cannot answer anything buried below it either, so the while loop can stop there. |
| 24 | while stack and pops(values[stack[-1]], value): |
| 25 | prev_idx = stack.pop() # Answered by the current value |
| 26 | answer[prev_idx] = i |
| 27 | # 3. Push The Current Index As Still Waiting: |
| 28 | # Whatever remains unanswered after the pops above is now the newest index waiting for its own answer, so it goes on top. |
| 29 | stack.append(i) |
| 30 | |
| 31 | # 4. Return The Collected Answers: |
| 32 | # Any index left on the stack when the scan ends never found a later value that answers it, so it keeps its -1. |
| 33 | return answer |
stack never increase from bottom to top, and every index still in stack has not yet seen a warmer day.Keep stack as the indices still waiting for a warmer day, and when temp beats the temperature on top, i is that index's answer: pop it and write answer[prev_idx] = i - prev_idx. Every index below the top has a temperature at least as high as the top's, so if temp does not beat the top it cannot beat anything below it; each index is therefore answered by the first warmer day to its right, and never earlier. The trap is storing temperatures instead of indices: the answer is a distance written into its own slot of answer, so push i, not temp.
See it run
Monotonic Stack, step by step
stack []answer [0, 0, 0, 0, 0, 0, 0, 0]
The top row is the temperatures. The column number is the day index. The bottom row is the stack: the left cell is the bottom, each cell holds a day index, and a blank cell is an unused slot.
tempthe day being read nowpoppedthe day taken off the stack, whose answer is written nowtopthe top of the stack after a poppushedthe day index that was just pushed
Start: stack is empty and every slot of answer is 0.
Gotcha 1 of 4
- The trap
Gotcha 1: Pushing
tempinstead of the indexiMistakestack.append(temp)Fixstack.append(i)What happens: The answer is a distance,
i - prev_idx, written intoanswer[prev_idx]. Both need the day's index, and a temperature cannot give it. Withtemponstack, the loop readstemperatures[stack[-1]]with a temperature as the index. That index is past the end of the list, so Python raises an IndexError.Example: temperatures = [30, 40, 50, 60]Mistake: raises IndexErrorFix: returns [1, 1, 1, 0]
- Each answer is the largest value inside a window of fixed size that also drops old items from the front, as in Sliding Window Maximum (LC 239), not the first larger value to the right. See Monotonic Deque
- You need how far each bar reaches on both sides to size a rectangle, as in Largest Rectangle in Histogram (LC 84), not just its next larger value. See Histogram Stack
Deep Dive
Why one pass finds the first warmer day
A stack is last in, first out: the newest item is the only one you can read or remove. In Daily Temperatures (LC 739), stack holds the day indexes that have not found a warmer day yet. The newest waiting day is on top.
The temperatures at those indexes never increase from bottom to top. A new day i is pushed only after every colder day on top was popped. So the day that stays below it is at least as warm as temp.
This order lets the loop stop early. If temp is not above the top, then it is not above any index lower in stack, because those days are at least as warm as the top. The while loop can stop at the first top that stays.
An index is popped by the first later day that is warmer. Suppose a day j between prev_idx and i was warmer than prev_idx. Then j would have popped every colder index above it and then prev_idx itself, because the stack order does not let j skip over it. So no such j exists.
Example: temperatures = [73, 74, 75, 71, 69, 72, 76, 73] gives [1, 1, 4, 2, 1, 1, 0, 0]. Day 2 has temperature 75. It waits until day 6 has temperature 76, so answer[2] = 6 - 2 = 4.
One trace: pop and write the distance, then push the index
The board replays the example from the previous section. The top row is temperatures. The bottom row is stack, and each cell in it holds a day index.
Days 0 to 4 build the stack. Day 1 (74) pops day 0 and writes answer[0] = 1. Day 2 (75) pops day 1 and writes answer[1] = 1. Then days 3 and 4 are pushed, because 71 and 69 are not above the top. Now stack is [2, 3, 4].
Day 5 has temperature 72. It pops day 4 (69) and writes answer[4] = 1. It pops day 3 (71) and writes answer[3] = 2. It stops at day 2 (75), because 72 is not above 75. Then stack is [2, 5].
Day 6 has temperature 76. It pops day 5 and writes answer[5] = 1. It pops day 2 and writes answer[2] = 4. Day 7 (73) pops nothing. Days 6 and 7 stay on stack, so their answers stay 0.
The trap: push the index, and pop only on a strictly warmer day
Push i, not temp. The answer is a distance written into its own slot: answer[prev_idx] = i - prev_idx. Both parts need the day index, and a temperature cannot give it. With temperatures on stack, the line temperatures[stack[-1]] reads a temperature as an index. For [30, 40, 50, 60] that is past the end of the list, so Python raises IndexError.
Pop only when temperatures[stack[-1]] < temp. Daily Temperatures (LC 739) asks for a strictly warmer day. With <=, a day with the same temperature pops the earlier day. For temperatures = [70, 70, 71], the correct answer is [2, 1, 0]. With <=, day 0 is popped by day 1, and the result is [1, 1, 0].
Check the start value of answer. Daily Temperatures (LC 739) wants 0 for a day with no warmer day, so answer = [0] * n. Next Greater Element I (LC 496) wants -1 for that case. Indexes still on stack at the end keep the start value, because the loop never writes their slot.
The cost, and how to change the question
Every index is pushed once and popped at most once. The while loop looks nested, but the total number of pops over the whole run is at most N. So the time is O(N) when one pops call costs O(1), and the space is O(N). A list of falling temperatures such as [90, 80, 70, 60] keeps all N indexes on stack.
To find the next smaller value, reverse the comparison: pop while temperatures[stack[-1]] > temp. To find the previous greater value, read stack[-1] after the pops and before the push. That is the index of the nearest earlier day that is at least as warm.
The template needs one property: if temp does not pop the top, it pops nothing below it. The comparisons <, <=, > and >= all have it. 132 Pattern (LC 456) does not have it, so it needs more than this template. Online Stock Span (LC 901) uses the same stack, but it answers one value at a time inside a class.
Sliding Window Maximum (LC 239) looks similar, but it also removes old items from the front when they leave the window. That needs a deque, and it is a different card.
60-Second Pitch
"For each day I need the first later day that is warmer. I scan once from left to right and keep a stack of day indexes that are still waiting. When today's temperature is above the temperature on top, that top day has its answer: I pop it and write today's index minus its index. I repeat that until the top is at least as warm. Then I push today's index. The stack never increases in temperature from bottom to top, so once today fails to beat the top, it cannot beat anything below it. Each index is pushed once and popped at most once, so the time is O(N). The space is O(N) in the worst case. Days left on the stack at the end get 0."
Common Questions
- The code has a loop inside a loop. Why is it
O(N)and not O(N^2)? The inner
whileloop pops items, and each index is pushed exactly once, so it can be popped at most once. Over the whole run the inner loop runs at mostNtimes in total. The pushes costN, the pops cost at mostN, so the total isO(N).- Why does
stackhold indexes and not temperatures? The answer is a distance,
i - prev_idx, and it is written intoanswer[prev_idx]. Both need the index. A temperature can be read from the index withtemperatures[index], so nothing is lost by storing the index.- How do you find the previous greater element instead of the next one?
Use the same loop. After the
whileloop pops the colder days,stack[-1]is the nearest earlier day that is at least as warm. Read it before you pushi. Ifstackis empty, there is no such day.- Could you scan from right to left instead?
Yes. Keep a stack of candidates. For each day, pop the candidates that are not warmer, then the top is the answer. The cost is the same,
O(N). The left to right form writes each answer at the moment of the pop, which is the form the card uses.- How is this different from Sliding Window Maximum (LC 239)?
Here each element waits for the first larger value to its right, and nothing leaves the structure except by being answered. In Sliding Window Maximum (LC 239) a window of fixed size moves, so old indexes must also be removed from the front. That needs a deque.
SWE Reasoning
Spot it
- The question asks, for each element, for the next or previous element that is greater or smaller, or for the distance to it.
- The wording says "next warmer", "first taller", "until a larger value" or "how many days to wait".
- A pair of loops would compare each element with every later element, which is O(N^2) time. The input is large enough to rule that out.
- Each element is waiting for one event that depends only on a later value.
- The comparison is
<,<=,>or>=. All four satisfy the precondition of the template.
The invariant, step by step
stackstarts empty. It will hold day indexes that have not found a warmer day yet.- Day
iarrives with temperaturetemp. Every index onstackis a day beforei. - While
temperatures[stack[-1]] < temp, the top day has found its first warmer day. Pop it and writeanswer[prev_idx] = i - prev_idx. - The loop stops at a top that is at least as warm as
temp. Every index below that top is also at least as warm, so none of them can be answered bytemp. - Push
i. The temperatures onstackstill do not increase from bottom to top. - When the scan ends, the indexes still on
stacknever found a warmer day. They keep their start value inanswer.
Traps
stack.append(temp). The loop needs a day index to read the temperature and to compute the distance. Pushi.stack[-1] < temp.stack[-1]is a day number. Comparetemperatures[stack[-1]]withtemp.<=in the pop. A day with an equal temperature is not warmer. It must not pop the earlier day.answer = [-1] * nfor LC 739. Days with no warmer day must be 0. Next Greater Element I (LC 496) is the problem that wants -1.- Treating indexes left on the stack at the end as an error. They are not an error. They are the days with no answer.