The problem
Given daily temperatures, for each day say how many days you must wait for a warmer day. Write 0 if a warmer day never comes.
Input: [73, 74, 75, 71, 69, 72, 76, 73] Output: [1, 1, 4, 2, 1, 1, 0, 0]
Picture it
Picture each day as a person waiting in a stack, holding a thermometer. A new day arrives. Every waiting person cooler than today finally gets their warmer day: they step off the stack and write down how long they waited. Then today joins the stack and waits too. People still on the stack at the end never got a warmer day.
How to recognise it
- For each position you need the next position to its right that is bigger (or smaller). This is the "next greater element" family.
- The answer for one day is decided by a later day, so days must wait until their answer arrives.
- When a warm day arrives, it answers every cooler day still waiting, starting with the most recent one. Waiting items that are resolved newest-first suggest a stack.
- Up to 10^5 days, so comparing every pair of days is too slow.
Start with brute force
For each day, walk forward until you find a warmer day, and record the distance.
def daily_brute(temps):
n = len(temps)
wait = [0] * n
for i in range(n):
for j in range(i + 1, n):
if temps[j] > temps[i]:
wait[i] = j - i
break
return wait
Time is O(n²) in the worst case and extra space is O(1) besides the output. A long cold spell at a constant 30 degrees never finds a warmer day, so every day scans to the end: with n = 10^5 that is about 5 × 10^9 comparisons.
From brute force to the idea
- Find the waste. The scans overlap. If day 3 at 71 degrees and day 4 at 69 degrees both wait, day 5 at 72 degrees is the answer for both, yet the brute force finds it twice in two separate walks.
- Keep the unanswered days. Walk once from left to right and hold a stack of positions whose warmer day has not arrived yet.
- The stack stays in order. A day only stays on the stack if no later day was warmer, so from bottom to top the temperatures never rise: the coolest waiting day is on top.
- Resolve from the top. When day
iwith temperaturetarrives, pop every waiting dayjwithtemps[j] < tand setwait[j] = i - j. Stop at the first day that is at least as warm; everything below it is warmer still, so they keep waiting too. - Then wait yourself. Push
i. Days still on the stack at the end never got warmer and keep their 0.
This is the key idea: a stack of unanswered days, coolest on top, lets each new day answer all the days it beats in one sweep.
The key idea
A “monotonic stack” keeps waiting days in decreasing temperature. Each day is pushed and popped once: O(n).
Python solution
def daily_temperatures(temps):
wait = [0] * len(temps)
stack = [] # days still waiting, coolest on top
for i, t in enumerate(temps):
while stack and temps[stack[-1]] < t:
j = stack.pop()
wait[j] = i - j # day j finally got warmer
stack.append(i)
return waitIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n²): a forward scan from every day | O(1) besides the output |
| Monotonic stack (shown code) | O(n): each position is pushed once and popped at most once, so the while loop runs at most n times in total | O(n): a non-rising run of days all wait on the stack |
Edge cases
- Empty list: returns
[]. LeetCode promises at least one day. - A single day (
[50]): returns[0]. - Equal temperatures (
[70, 70]): returns[0, 0]. The comparison is strict, so an equally warm day does not count, and the first 70 keeps waiting under the second. - Equal then warmer (
[70, 70, 75]): returns[2, 1, 0]; the 75 pops both days. - Rising (
[30, 40, 50, 60]):[1, 1, 1, 0]. Each day is popped by the next one. - Falling (
[60, 50, 40, 30]): all zeros, and the stack grows to n items.
Common mistakes
- Storing temperatures on the stack instead of positions. You need the position to compute
i - jand to write intowait[j]. - Popping with
<=instead of<. A day of equal temperature would then answer the earlier day, which the problem forbids. - Starting
waitas an empty list and only writing answers for popped days. Days still on the stack at the end then have no entry; filling the list with 0 up front covers them.
For each day, return how many days ago the most recent strictly warmer day was, or 0 if there was none. For [73, 74, 75, 71, 69, 72, 76, 73] the answer is [0, 0, 0, 1, 1, 3, 0, 1]. Describe your approach, then write it if you like.
Compare with our answer
Now the answer lies to the left, so each day reads it from the stack at the moment it arrives. Pop every earlier day that is not warmer (they can never be the answer for any later day either, because today is at least as warm and closer). Whatever is left on top is the most recent warmer day.
def since_warmer(temps):
out = [0] * len(temps)
stack = [] # positions, warmest at the bottom
for i, t in enumerate(temps):
while stack and temps[stack[-1]] <= t:
stack.pop()
out[i] = i - stack[-1] if stack else 0
stack.append(i)
return out
Time O(n), space O(n).
A strong answer mentions: why popped days are useless for every later day, why the pop uses <= here (a day of equal temperature is not strictly warmer), and that the answer is read after popping and before pushing.
1. For each day's share price, you must find how many days until the price first drops below today's. Which approach fits best?
It is the same "next smaller element" question with the comparison flipped, so a monotonic stack answers it in O(n). The later prices are not sorted, so binary search does not apply, and a running minimum ignores which day comes first.
2. Why is the shown code O(n) even though it has a while loop inside a for loop?
Total pops can never exceed total pushes, which is n. A single new day can pop many days, but those days are gone for good. Equal temperatures can stay on the stack together, so it is not limited to 71 items.
3. A learner writes while stack and temps[stack[-1]] <= t:. Which input now gives a wrong answer?
With <= the second 70 pops the first and records a wait of 1, but 70 is not warmer than 70. The other inputs contain no repeated temperature, so < and <= behave the same.
Score 60% or more and the lesson is marked complete.