Example 1
ready- Input
temperatures = [ 73, 74, 75, 71, 69, 72, 76, 73 ]- Expected
[ 1, 1, 4, 2, 1, 1, 0, 0 ]- Why
- each value counts forward to its first strictly warmer day
Daily Temperatures
35 min · dailyTemperatures()mediumOpen in LeetCode #739 ↗
Knowing that warmer weather is coming isn't enough — you want to know exactly how long you'll wait.
You're given an integer array temperatures, where each value records one day's
temperature. Return an array waits of the same length. For each day i, waits[i]
must be the number of days until the first later day with a strictly higher temperature.
Use 0 when no warmer day follows.
A few ground rules:
- Equal temperatures aren't warmer.
- You want the first warmer day, not the warmest future day.
- The last day always receives
0because no day follows it.
Constraints
1 <= temperatures.length <= 100_000-100 <= temperatures[i] <= 100
Hints
Start with the direct question
For each day, scan forward until you find a higher temperature. This is correct. Count the comparisons for 100,000 equal days before deciding it's fast enough.
Keep only unresolved days
As you move forward, some earlier days still haven't seen anything warmer. When today's temperature beats one of them, today's index immediately gives its wait.
Make the newest day easy to check
A monotonic stack stores items in a maintained order. Keep unresolved day indices
so their temperatures run from hotter to cooler toward the top. Pop while today is
warmer, recording today - earlier for every popped index.
Follow-up
If temperatures arrived one day at a time, which answers could you emit immediately, and which days would still need to wait on your stack?
Visible cases
Examples
Example 2
ready- Input
temperatures = [ 30, 40, 50, 60 ]- Expected
[ 1, 1, 1, 0 ]- Why
- every day except the last is followed immediately by a warmer one
Example 3
ready- Input
temperatures = [ 90, 80, 70 ]- Expected
[ 0, 0, 0 ]- Why
- a falling forecast never produces a warmer future day
Interview signal
Asked at
AmazonGoogleMeta
Scan every future day
Ask the question exactly as written. For each day, walk right until the first strictly
warmer temperature appears. Record the distance and stop that inner scan. If it never
appears, the answer stays 0.
def daily_temperatures(temperatures: list[int]) -> list[int]:
waits = [0] * len(temperatures)
for day in range(len(temperatures)):
for future in range(day + 1, len(temperatures)):
if temperatures[future] > temperatures[day]:
waits[day] = future - day
break
return waitsThis behaves well when a warmer day is nearby. Equal or steadily falling temperatures force almost every scan to reach the end.
Time O(n²) in the worst case. Space O(1) beyond the required result array.
Monotonic index stack
A monotonic decreasing stack keeps values in non-increasing order from bottom to top. Store day indices rather than temperatures, because an answer needs the distance between two positions.
The stack contains days that still need a warmer future day. When today's temperature is higher than the temperature at the top index, today resolves that older day. Pop it and record the distance. Keep popping while today's value is strictly higher; then push today as a new unresolved day.
def daily_temperatures(temperatures: list[int]) -> list[int]:
waits = [0] * len(temperatures)
unresolved: list[int] = []
for today, temperature in enumerate(temperatures):
while unresolved and temperature > temperatures[unresolved[-1]]:
earlier = unresolved.pop()
waits[earlier] = today - earlier
unresolved.append(today)
return waitsWhy is today the first warmer day for each popped index? That index stayed unresolved through every day between it and today. If an earlier warmer value existed, it would already have popped the index.
Equal values remain on the stack because the comparison is strict. Any indices left at
the end correctly keep their initial 0.
Time O(n) — each index is pushed once and popped at most once. Space O(n) for the unresolved stack.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
[ 1, 1, 4, 2, 1, 1, 0, 0 ]
Run: visible + custom · Submit: full suite