You have a list of daily temperatures. For each day, work out how many days you'd wait until a strictly warmer day. If no warmer day comes later, use 0. Return a list with one number per day.
Write days_until_warmer(temps) in Python or daysUntilWarmer(temps) in JavaScript.
Runs privately in your browser. Nothing is sent to a server.Ctrl/⌘ + Enter to run · Esc then Tab to leave the editor
Write your function, then run it against 20 tests.
Breakdown
Stuck? Reveal one step at a time, and try again after each one.
Brute force
For each day, scan forward until you find a warmer day. That's O(n²) when temperatures mostly fall (every scan goes to the end). Can you find each day's answer while passing through the list just once?
Step 2
Who is still waiting?
As you walk forward, keep the days that haven't found a warmer day yet. When a new day arrives, it may be the answer for several of them at once.
Step 3
Which waiting days does a new day answer?
The waiting days always have temperatures that don't increase from oldest to newest (a warmer day would already have answered the older, cooler ones). So the coolest waiting day is the most recent. Compare the new day against the most recent waiting day: if the new day is warmer, that day's wait is over. Repeat.
Step 4
That's a stack
Keep waiting days on a stack (store indexes). For each new day, pop every day it's warmer than, setting answer[popped] = today - popped. Then push today. Days left on the stack at the end keep their 0.
Step by step1 / 4
i
18
0
17
1
21
2
d0 · 18↓push
empty
Day 0 (18): nothing is waiting. Push it.
Solution
Give it a real try first: you learn far more from a wrong attempt than from reading the answer.
Start with answer full of zeros and an empty stack of indexes. For each day i, while the stack's top day is cooler than temps[i], pop it and set its answer to i - top. Then push i.
python
1def days_until_warmer(temps):
2 answer = [0] * len(temps)
3 waiting = [] # indexes of days still waiting for a warmer day
↑days with no warmer day yet
4 for i, t in enumerate(temps):
5 while waiting and temps[waiting[-1]] < t:
↑today is warmer than the latest waiter
6 day = waiting.pop()
7 answer[day] = i - day
↑their wait is over
8 waiting.append(i)
↑now today waits too
9 return answer
javascript
1function daysUntilWarmer(temps) {
2 const answer = new Array(temps.length).fill(0)
3 const waiting = [] // indexes of days still waiting for a warmer day
↑days with no warmer day yet
4 for (let i = 0; i < temps.length; i++) {
5 while (waiting.length && temps[waiting[waiting.length - 1]] < temps[i]) {
↑today is warmer than the latest waiter
6 const day = waiting.pop()
7 answer[day] = i - day
↑their wait is over
8 }
9 waiting.push(i)
↑now today waits too
10 }
11 return answer
12}
Complexity
TimeO(n)SpaceO(n)
O(n) time: each day is pushed once and popped at most once. O(n) space for the stack and the answer.