Daily Temperatures

Medium#739

You get the temperature of each day in a row. For every day, say how many days you have to wait for a strictly warmer one; if no warmer day ever comes, the answer is 0. Our example: [64, 61, 61, 59, 66, 62, 63] gives [4, 3, 2, 1, 0, 1, 0].

739 Daily TemperaturesWalkthrough · 1×

Example: [64, 61, 61, 59, 66, 62, 63]: for each day, how many days until a warmer one. Under the temperatures are the waits; the stack keeps the days still waiting, their temperatures falling or equal towards the top.

064161261359466562663tempswait0000000stack—
not reachedtodaywaiting on the stacktop being checkedwarmer day found

Every wait starts at 0: the answer for a day that never gets warmer

01/39
restart · back · play · step
Speed
1function dailyTemperatures(temps):
2 wait = list of len(temps) zeros
3 stack = empty stack // days still waiting
4 for day from 0 to len(temps) - 1:
5 while stack not empty and day is warmer than top:
6 prev = pop from stack
7 wait[prev] = day - prev
8 push day onto stack
9 return wait
state
wait
[0, 0, 0, 0, 0, 0, 0]
stack
–
day
–
prev
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. A day waits on the stack until the first warmer day comes. That day pops it at once, so the distance between the two is exactly its wait.
  2. Every day on the stack is not warmer than the one under it: a warmer day would have popped it. So when today is not warmer than the top, it is not warmer than anything below it either, and the loop can stop.
  3. An equal temperature does not pop: the problem asks for a strictly warmer day. Days still on the stack at the end never got one and keep their 0.

Complexity

Time O(n): each day is pushed once and popped at most once, so the inner loop runs at most n times in all. Memory O(n) for the stack and the answer.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.