Days until a warmer day
A weather app that prints "warmer in 4 days" under each day of a forecast answers one question for every position of a list: how far to the right is the first larger value? Many problems ask for the nearest larger or smaller value on one side of every position, and a stack answers each of them in a single pass over the list. We start with the weather version.
You get a list temperatures of daily temperatures. For each day, return how many days you have to wait after it for a strictly warmer temperature. If no warmer day comes, return 0 for that day.
Constraints
-
len(temperatures) -
temperatures[i]
Sample 1 · Input
temperatures = [73,74,75,71,69,72,76,73]
Output
[1,1,4,2,1,1,0,0]
Sample 2 · Input
temperatures = [30,40,50,60]
Output
[1,1,1,0]
Sample 3 · Input
temperatures = [30,60,90]
Output
[1,1,0]
Number the days from 0. In the first sample, day 2 has temperature 75. Days 3, 4 and 5 are colder, at 71, 69 and 72, and day 6, at 76, is the first warmer one, so day 2 waits days. Nothing after day 6 or day 7 is warmer, so they get 0.
The direct method looks ahead from each day until it finds a warmer one. That is quick on the sample, but consider a list in which the temperature never rises, such as 100,000 days at 50 degrees. No lookahead finds a warmer day, so each one runs to the end of the list. The first day is compared with 99,999 later days, the second with 99,998, and so on:
At about simple operations a second, that is around 50 seconds. The lookahead is slow because it reads the same days many times. Even in the sample, the lookahead from day 2 reads days 3, 4, 5 and 6, and then the lookaheads from days 3 and 4 read days 4 and 5 again.
The list of waiting days
To avoid those repeated lookaheads, we go through the list once, from left to right, and keep a list of the days that are still waiting, meaning that no warmer day has come for them yet. Each new day may be the warmer day that some of them are waiting for.
Follow the sample up to day 4. Day 0, at 73, starts waiting. Day 1, at 74, is warmer, so day 0 gets its answer, , and stops waiting, and day 1 starts. Day 2, at 75, does the same to day 1. Day 3, at 71, is not warmer than day 2, and day 4, at 69, is not warmer than day 3, so both join the list and nobody gets an answer. The waiting days are now:
waiting day 2 3 4temperature 75 71 69The temperatures fall from left to right, and they cannot rise at any point of the scan. If a waiting day were warmer than a day that started waiting before it, it would have been that earlier day's answer, and the earlier day would not be waiting any more. So the waiting days, in the order they arrived, never get warmer.
Because of this order, a new day answers waiting days from the newest one back. Day 5 is at 72. That is warmer than the newest waiting day, day 4 at 69, so day 4 gets . The next newest is day 3 at 71, also colder than 72, so day 3 gets . Then comes day 2 at 75, which is warmer than 72, and here we can stop: every day that has waited longer than day 2 is at least as warm as day 2, so none of them gets an answer from day 5 either. Day 5 then joins the list as its newest member.
A new day removes waiting days only from the newest end of the list, one after another, and is then added at that same end. A list that changes at one end only is a stack, with the newest waiting day on top.
The table runs the scan on all eight days of the sample. The stack is written with its bottom entry first.
| Day | Temperature | Popped, with its wait | Stack after the push |
|---|---|---|---|
| 0 | 73 | none | 0 |
| 1 | 74 | day 0 waits 1 | 1 |
| 2 | 75 | day 1 waits 1 | 2 |
| 3 | 71 | none | 2, 3 |
| 4 | 69 | none | 2, 3, 4 |
| 5 | 72 | day 4 waits 1, day 3 waits 2 | 2, 5 |
| 6 | 76 | day 5 waits 1, day 2 waits 4 | 6 |
| 7 | 73 | none | 6, 7 |
Days 6 and 7 are still on the stack when the list ends. No warmer day came for them, so their answer is 0, and the answers together are [1, 1, 4, 2, 1, 1, 0, 0].
A stack like this one, whose values stay in sorted order from bottom to top, is called a monotonic stack; monotonic means moving in one direction only. The scan keeps the order by popping every day colder than the new one before it pushes the new one.
The scan in code
The stack holds day numbers and not temperatures. A day number gives both things the scan needs: the temperature to compare, temperatures[day], and the place in answer to write the wait.
def daily_temperatures(temperatures):
answer = [0] * len(temperatures)
waiting = [] # days with no warmer day yet
for day in range(len(temperatures)):
while waiting and temperatures[day] > temperatures[waiting[-1]]:
earlier = waiting.pop()
answer[earlier] = day - earlier
waiting.append(day)
return answer
print(daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]))Prints [1, 1, 4, 2, 1, 1, 0, 0], the first sample's answer.
The while loop is the run of pops from the table. It stops at the first waiting day that is at least as warm as today, or when the stack is empty. The comparison is > and not >= because the problem asks for a strictly warmer day, so a day with the same temperature leaves the earlier day waiting.
answer starts as all zeros, so the days that are still on the stack at the end already hold the 0 the problem asks for.
Cost of the scan
- Looking ahead from every day
time - Up to comparisons: 4,999,950,000 for 100,000 days that never warm up.
- One pass with a stack
time - Each day is pushed once and popped at most once. That is at most stack operations: 200,000 for 100,000 days.
- Memory for the stack
- When the temperature never rises, no day is popped, and all days are on the stack at the end.
A while loop inside a for loop can mean steps, but this scan stays linear. One day can pop many others, as day 6 popped two, but a popped day does not come back to the stack, so the whole scan makes at most pops, however they are spread over the days.
Make the pushes and pops yourself
In this widget you run the scan on the sample. As each day arrives, choose Pop the top while the day is warmer than the one on top of the stack, and Push today once the stack is empty or its top is at least as warm. Count your stack operations against the bound of .
Worked example
Trace the scan
The trace runs the code on the same sample and shows the stack of day numbers after every step. Its other three lists have a day that pops two others, two equal days that both keep waiting, and falling temperatures that leave every day on the stack.
The stack keeps indices whose warmer day is still unknown. Their temperatures never increase from bottom to top.
Change the example input
Current result: [1,1,4,2,1,1,0,0]
The nearest smaller value to the left
In Daily Temperatures, each day looked to its right for a larger value. The mirror question is: for each index, which is the nearest index to its left that holds a smaller value? CSES has this task as the problem Nearest Smaller Values, and the largest-rectangle problem further down needs it. Take this list:
index 0 1 2 3 4 5heights 2 1 5 6 2 3For index 3, which holds 6, the nearest smaller value to the left is the 5 at index 2. For index 4, which holds 2, the 6 and the 5 are not smaller, and the nearest smaller value is the 1 at index 1. Indices 0 and 1 have nothing smaller to their left, and for them we will record .
The same kind of stack finds these answers, with one difference. In Daily Temperatures an entry received its answer at the moment it was popped; here the arriving index reads its own answer off the stack. The stack holds the indices that could still be the answer for some later index, and when index i arrives we do three things:
- Pop while the value on top is greater than or equal to
heights[i]. - If the stack is now empty, nothing to the left is smaller, and the answer is . Otherwise the answer is the index on top.
- Push
i.
The pops in step 1 are safe because a popped index can never be an answer again. Suppose i pops index p. Then heights[i] is no larger than heights[p], and i lies further to the right. For any later index, if p holds a smaller value then so does i, and i is nearer. After the pops, the top is smaller than heights[i], and so is everything below it, since each value was pushed onto a smaller one. Of these smaller values the top is the nearest, because indices were pushed from left to right.
On our list the scan goes like this, with the stack written bottom first:
i | heights[i] | Popped | Answer | Stack after the push |
|---|---|---|---|---|
| 0 | 2 | none | 0 | |
| 1 | 1 | 0 | 1 | |
| 2 | 5 | none | 1 | 1, 2 |
| 3 | 6 | none | 2 | 1, 2, 3 |
| 4 | 2 | 3, 2 | 1 | 1, 4 |
| 5 | 3 | none | 4 | 1, 4, 5 |
At the end the stack holds indices 1, 4 and 5, with the values 1, 2 and 3. The values on this stack rise from bottom to top, the opposite direction from the waiting days, and it is a monotonic stack as well.
Step 1 pops equal values too, because the answer has to be strictly smaller. In the list [2, 2], nothing to the left of the second 2 is smaller than it, so the first 2 must not be left on top to be read as its answer. It is popped, and the answer is . The first 2 is not needed later either, since the second 2 holds the same value nearer to every later index.
def nearest_smaller_left(heights):
left = []
stack = [] # indices whose values rise from bottom to top
for i in range(len(heights)):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
left.append(stack[-1] if stack else -1)
stack.append(i)
return left
print(nearest_smaller_left([2, 1, 5, 6, 2, 3]))Prints [-1, -1, 1, 2, 1, 4], the Answer column of the table.
As before, each index is pushed once and popped at most once, so the scan takes time.
The largest rectangle under a histogram
The next problem is solved by finding the nearest smaller value on both sides of every index.
You get a list heights of bar heights. The bars have width 1 and stand side by side. Return the area of the largest rectangle that fits inside the bars.
Constraints
-
len(heights) -
heights[i]
Sample 1 · Input
heights = [2,1,5,6,2,3]
Output
10
Sample 2 · Input
heights = [2,4]
Output
4
The first sample is the list [2, 1, 5, 6, 2, 3] from the nearest smaller scan. Its bars of height 5 and 6 hold a rectangle of height 5 and width 2, with area 10, and no rectangle under these bars is larger.
A rectangle is fixed by its leftmost and its rightmost bar, and it can be as tall as the shortest bar between them. Trying every pair of ends is too slow: 100,000 bars have pairs of ends, counting the rectangles that are one bar wide.
We can go through the bars instead of the pairs. For each bar i, take the widest rectangle of height heights[i] that contains bar i. That gives rectangles, and the largest rectangle of all is one of them.
To see why, let j be the shortest bar inside the largest rectangle. The rectangle cannot be taller than heights[j], and if it were lower it could be raised, so its height is heights[j]. It contains bar j and has that height, so it is no wider than the rectangle we take for bar j, which is the widest such rectangle. That rectangle has at least the same area, so the largest area is found among our rectangles.
The rectangle for bar i extends to the left until it meets a bar lower than heights[i], and to the right in the same way. Write left[i] for the index of the nearest lower bar on the left, or if there is none, and right[i] for the nearest lower bar on the right, or if there is none. The rectangle covers the bars strictly between the two, so its area is
left is exactly the nearest smaller scan of the previous part. right is the same scan run from the right end of the list, with in place of :
def largest_rectangle_area(heights):
n = len(heights)
left = [-1] * n # nearest lower bar on the left, or -1
stack = []
for i in range(n):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
if stack:
left[i] = stack[-1]
stack.append(i)
right = [n] * n # nearest lower bar on the right, or n
stack = []
for i in range(n - 1, -1, -1):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
if stack:
right[i] = stack[-1]
stack.append(i)
best = 0
for i in range(n):
best = max(best, heights[i] * (right[i] - left[i] - 1))
return best
print(largest_rectangle_area([2, 1, 5, 6, 2, 3]))
print(largest_rectangle_area([2, 4]))Prints 10 and then 4, the two samples' answers.
On the first sample, left is [-1, -1, 1, 2, 1, 4] and right is [1, 6, 4, 4, 6, 6], which gives the six areas 2, 6, 10, 6, 8 and 3. The largest is 10, from the bar at index 2. Each of the two scans pushes every index once and pops it at most once, so 100,000 bars take at most 400,000 stack operations.
Deeper read: the four nearest-value questions
So far we have found the next greater value to the right and the nearest smaller value on each side. There are four questions of this kind (greater or smaller, to the left or to the right), and one scan from left to right can answer any of them. Two choices decide which.
- Which entries a new value pops. To find greater values, pop the entries that are smaller than the new value, so that the stack falls from bottom to top. To find smaller values, pop the entries that are greater, so that it rises.
- Who gets the answer. An entry is popped by the first value to its right that is larger than it (or smaller, in a scan for smaller values), so the popped entries receive the answers to the right. The new value, after its pops, finds on top the nearest value to its left that it could not pop, so the new values read the answers to the left.
Whether equal values are popped decides how ties count, and one scan cannot be strict on both sides. If equal values are popped, as in the nearest smaller scan, each new value reads the nearest strictly smaller value to its left, while each popped entry has met the first value to its right that is smaller than or equal to it. If equal values stay, it is the other way round: new values read the nearest smaller-or-equal value to their left, and popped entries meet the first strictly smaller value to their right.
The histogram solution runs a second scan from the right so that both sides are strict. A single scan that pops equal bars also finds the largest area: of the equal bars inside the largest rectangle, the last one still gets the full width.
The maximum of a sliding window
The last problem on this page keeps the idea of popping entries that can never be the answer again, and adds one thing: an entry can also stop being useful because the window has moved past it.
You get a list nums and a window size k. A window covering k consecutive values starts at the left end and slides right one position at a time until it reaches the right end. Return the largest value in each window, in order.
Constraints
-
len(nums) -
nums[i] -
len(nums)
Sample 1 · Input
nums = [1,3,-1,-3,5,3,6,7], k = 3
Output
[3,3,5,5,6,7]
Sample 2 · Input
nums = [1], k = 1
Output
[1]
In the first sample the windows are [1, 3, -1], [3, -1, -3], [-1, -3, 5], [-3, 5, 3], [5, 3, 6] and [3, 6, 7], and their maximums are 3, 3, 5, 5, 6 and 7.
Taking the maximum of each window separately reads values for each of the windows. With and that is
or about 25 seconds of work. A read is wasted when its value cannot be a window maximum again. Look at the sample at the moment the 5 at index 4 arrives. The earlier values 3, and at indices 1 to 3 are all smaller than 5, and each of them leaves the window before the 5 does. From now on, every window that contains one of them contains the 5 as well, so none of the three can be a window maximum again.
[-1, -3, 5].So we keep only the indices that could still be a maximum. They go in a deque, with the oldest at the front. For each new index i:
- Remove indices from the back while their value is smaller than
nums[i]. They can no longer be a maximum. - Add
iat the back. - The window now covers the indices from
i - k + 1toi. If the index at the front isi - kor less, it has left the window, so remove it from the front. - If
iis at leastk - 1, the window is full, and the value at the front is the maximum of the current window.
Step 1 keeps the values in the deque from rising from front to back, like the temperatures of the waiting days, so the largest value in the window is always at the front. A deque kept in sorted order like this is called a monotonic queue. It is a monotonic stack that can also lose its oldest entry, which is why it needs a deque: the pushes and pops of the stack happen at the back, and an index that has left the window is removed at the front.
The back needs a loop and the front only one test, because the window moves one index at a time, so at most one index, i - k, leaves it in each step.
The deque step by step
Here are the four steps, run at each index of the first sample, with . The deque is written front first.
i | nums[i] | Removed from the back | Deque after | Window maximum |
|---|---|---|---|---|
| 0 | 1 | none | 0 | no window yet |
| 1 | 3 | 0 | 1 | no window yet |
| 2 | none | 1, 2 | 3 | |
| 3 | none | 1, 2, 3 | 3 | |
| 4 | 5 | 3, 2, 1 | 4 | 5 |
| 5 | 3 | none | 4, 5 | 5 |
| 6 | 6 | 5, 4 | 6 | 6 |
| 7 | 7 | 6 | 7 | 7 |
In this sample step 3 removes nothing: every index is removed from the back by a larger value before step 3 can reach it. To see the front at work, take the falling list [5, 4, 3, 2, 1] with . No new value is larger than an old one, so the back keeps everything. When index 2 arrives, the deque holds 0, 1 and 2. The front index, 0, equals , so it has left the window [4, 3] and is removed, and the front becomes index 1 with the value 4. The same happens at every later step, and the output is [5, 4, 3, 2].
This is also the reason the deque holds indices and not values: an index tells us when its value has left the window.
def max_sliding_window(nums, k):
window = deque() # indices; their values never rise from front to back
answer = []
for i in range(len(nums)):
while window and nums[window[-1]] < nums[i]:
window.pop()
window.append(i)
if window[0] <= i - k:
window.popleft()
if i >= k - 1:
answer.append(nums[window[0]])
return answer
print(max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3))
print(max_sliding_window([5, 4, 3, 2, 1], 2))Prints [3, 3, 5, 5, 6, 7] for the first sample and [5, 4, 3, 2] for the falling list.
Each index enters the deque once and leaves it at most once, so the scan makes at most deque operations: 200,000 for , against the 2,500,050,000 reads of taking each maximum separately. The deque holds at most indices at a time. The Sliding window lesson comes back to this deque for windows whose length changes.
Common mistakes with monotonic stacks and queues
Popping a waiting day when the new temperature is equal (
>=where Daily Temperatures needs>).- Where it breaks
- For
[22, 22, 23]the second 22 pops the first, and the function returns[1, 1, 0]. A day at 22 is not warmer than a day at 22, and the answer is[2, 1, 0]. - The fix
- Use
>. The answer needs a strictly warmer day, so a day may pop only colder ones.
Writing
ifwhere the pops needwhile.- Where it breaks
- For
[30, 20, 25, 40]the 40 is the first warmer day for both day 2 and day 0. Withifit pops only day 2, and the function returns[0, 1, 1, 0]where the answer is[3, 1, 1, 0]. - The fix
- Keep popping until the stack is empty or its top is at least as warm as today.
Popping only strictly taller bars in the histogram scans (
>where they need>=).- Where it breaks
- For
[2, 2]each bar then treats the other as a lower bar, both rectangles get width 1, and the function returns 2 where the answer is 4. - The fix
- Pop bars that are taller or equal, so that the index left on top holds a strictly lower bar.
Letting the front of the window deque stay one step too long (writing
window[0] < i - k).- Where it breaks
- For
[5, 4, 3, 2, 1]with , index 0 is still at the front when index 2 arrives, and the output is[5, 5, 4, 3]where the answer is[5, 4, 3, 2]. - The fix
- The window ending at
istarts ati - k + 1, so the front leaves as soon as it isi - kor less.
Recall Run the nearest smaller scan on `[3, 1, 4, 1, 5]`. What is the stack after each index, and what are the five answers?
Index 0 finds an empty stack and gets ; the stack becomes 0. Index 1, with the value 1, pops index 0 and also gets ; the stack is 1. Index 2, with the value 4, pops nothing and reads index 1 from the top; the stack is 1, 2.
Index 3 holds 1. It pops index 2, whose 4 is larger, and then index 1, whose 1 is equal, because an equal value is not strictly smaller. The stack is empty, so the answer is , and the stack becomes 3. Index 4, with the value 5, reads index 3 from the top, and the stack ends as 3, 4. The answers are [-1, -1, 1, -1, 3].