Daily Temperatures
A decreasing stack of indices resolves each 'next warmer day' exactly once.
Stack Trace
Problem
Given an array of daily temperatures, return an array where each position tells how many days pass before a warmer temperature appears. If no later day is warmer, store 0 for that position. The answer must preserve the original order of the days.
Examples
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]
The Goal
For each day, count the days until a warmer one. If no later day is warmer, the answer is 0.
For [73, 74, 75, 71, 69, 72, 76, 73], day 2 (75°) waits 4 days for 76°, and the last two days never get a warmer day. The answer is [1, 1, 4, 2, 1, 1, 0, 0].
Scanning ahead from every day rereads the same days. One pass with a stack is enough.
A wait, not a temperature
answer[i] is how many days pass from day i to the first later day that is strictly warmer, or 0 if none is.
A day just as warm doesn't count.
Key Idea: A Stack of Waiting Days
Keep the days still waiting for a warmer one on a stack. Their temperatures never rise from bottom to top.
When a new day is warmer than the top, the top's wait is over: pop it and write the gap. Keep popping while the new day is warmer. The first top that isn't colder stops it, and every day under that one is at least as warm.
Then push the new day. It waits too.
From bottom to top, temperatures stay the same or fall.
After day 4: 75, 71, 69.
The Algorithm
def daily_temperatures(temperatures):
answer = [0] * len(temperatures)
stack = [] # days still waiting for a warmer one
for i, t in enumerate(temperatures):
while stack and temperatures[stack[-1]] < t:
j = stack.pop()
answer[j] = i - j
stack.append(i)
return answerThe comparison is strict: a day as warm as the top doesn't pop it.
Days still on the stack at the end keep their 0.
Walkthrough
Run it on [73, 74, 75, 71, 69, 72, 76, 73].
74° pops day 0, and 75° pops day 1: each waited 1 day. 71° and 69° are colder, so the stack grows to days 2, 3 and 4.
72° on day 5 pops day 4 (1 day) and day 3 (2 days), and stops at day 2's 75°. 76° pops day 5 and day 2, which waited 4 days. Days 6 and 7 keep 0.
Checkpoint · predict the next step
Step 13 of 40 on the stage: Push day 2. It waits for a warmer day.
i on 75 (index 2) · stack = [2] · answer = [1, 1, 0, 0, 0, 0, 0, 0]
Pitfalls
- Pop only while the new day is strictly warmer. With
<=, equal days pop each other, and[70, 70, 70, 70]would get waits instead of all zeros. - Store days, not temperatures, so the wait is a subtraction.
- Push every day, after the popping.
- A falling run, like
[90, 80, 70, 60, 50], never pops at all. Every day stays on the stack and keeps 0.
Why does scanning ahead from every day get slow?
Complexity
Each day is pushed once and popped at most once. One day can pop several, but across the whole scan there are at most n pops, so time is O(n). The example pops 6 of its 8 days.
On a falling run the stack holds every day, so extra space is O(n).
One pass, each day pushed and popped at most once
- Scan the daysEach day once.dominantO(n)
- PushesEach day goes on once.dominantO(n)
- PopsEach day comes off at most once.dominantO(n)
- Scan ahead from every dayThe approach the stack replaces.O(n^2)
| n | 10 | 100 | 1,000 | 10,000 |
|---|---|---|---|---|
| O(n) | 10 | 100 | 1K | 10K |
Linear, because no day is pushed or popped twice.
In short
Keep a stack of indices with decreasing temperatures. When a warmer day arrives, pop every colder index and record the day gap for each. Each index is pushed and popped once, so the whole thing is linear.
Common mistake
Scanning forward for each day (O(n²)) instead of letting the monotonic stack resolve answers as it pops.