LC739: Daily Temperatures

Mediummonotonic stack

The brute force works, but at 100,000 days it is about 5 billion comparisons. A stack of the days still waiting does it in O(n).

The problem

Given a list of daily temperatures, return how many days you wait after each day for a warmer one, or 0 if no warmer day comes. For [73,74,75,71,69,72,76,73] the answer is [1,1,4,2,1,1,0,0].

See it

Example 1 as thermometers, one per day. Every answer starts unknown.
The finished answer, [1,1,4,2,1,1,0,0]: days 6 and 7 never see a warmer day, so they stay 0.
Brute force scans forward from every day. Flat temperatures are its worst case: about 5 billion comparisons at 100,000 days.
The days still waiting form a stack that never gets warmer toward the top, a monotonic stack.
Day 5 (72) checks the top of the stack, where 75, 71 and 69 are still waiting.
The stack solution from the video, the same code as below.
The trade: brute force is O(n²) time and O(1) space; the stack is O(n) time and O(n) space.

The code

1def dailyTemperatures(temps):
2    answer = [0] * len(temps)
3    stack = []  # waiting indices
4 
5    for i in range(len(temps)):
6        while (stack and temps[i]
7              > temps[stack[-1]]):
8            j = stack.pop()
9            answer[j] = i - j
10        stack.append(i)
11 
12    return answer

The stack holds indices, not temperatures: when today i is warmer than waiting day j, the answer for j is i - j. The comparison is strict (>), so an equal day is not a warmer one.

Complexity

Time: O(n). Each index is pushed once and popped at most once.
Space: O(n) extra. The stack grows while temperatures never go up; with all-equal days it holds every index.
Brute force: O(n²) time in the worst case, about 5 billion comparisons at 100,000 days. On the 8-day example the two are nearly tied, 11 comparisons to 10; the gap only shows at scale.

Edge cases

All equal: [70,70,70,70] gives [0,0,0,0], because equal is not warmer.
Equal, then warmer: [70,70,71] gives [2,1,0].
A single day has no later day, so its answer is [0].
Temperatures that never rise give all zeros, and they fill the stack: its worst case for space.

Where you'd actually use this

Mostly in interviews. Daily Temperatures is asked at companies like Amazon and Google (source: Educative) because the obvious scan works but is O(n²), and getting to O(n) takes a new idea: keep a stack of the days still waiting for a warmer one.

Early access

Join Cohort 0

The first group to try the full site before anyone else. We start with algorithms and data structures, then go further into computer science.

Run your own code and watch every step
See the exact step where your logic breaks
Vote on what we animate next
Get the private link before public launch