Daily Temperatures
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
For each day, find how many days you must wait until a warmer day (0 if never).
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1For day i, you look to the right for the first bigger value. Which days are still waiting at any moment?
- Hint 2Keep waiting days on a stack; a warmer day pops the colder ones.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Every day is a person standing in a queue, waiting for a warmer day to arrive. When a hot day comes, it "settles" every colder day still waiting: those days stop waiting and note how many days they waited. Colder days still waiting are kept in a pile with the coldest at the bottom... newest on top; a hot day clears the pile from the top while the top is colder than it.
- The obvious way
For each day scan forward until a warmer day: O(n²).
- The key insight
Walk through the days keeping a stack of days that have not found a warmer day yet; their temperatures are decreasing from bottom to top. A new day that is warmer than the top day answers that day (days waited = today - that day) and pops it; repeat while it is still warmer. Then today waits on the stack. Every day is pushed and popped once.
- The algorithm
- Answers all 0; an empty stack of waiting days.
- For each day, while the stack's top day is colder than today: pop it and record (today's number - that day's number).
- Then put today on the stack.
- Days still on the stack never found a warmer day: they stay 0.
Watch it run
Exampletemps = [73, 74, 75, 71, 69, 72, 76, 73]
Day 0 (73) waits.
waiting: 73
Where people slip
- Store day INDEXES on the stack (not temperatures): you need them to compute the waiting time.
- Use a strict comparison (<): an equal temperature is not warmer.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def daily_temperatures(temps):
answer = [0] * len(temps)
waiting = [] # days still waiting for a warmer day
for today, temp in enumerate(temps):
while waiting and temps[waiting[-1]] < temp:
day = waiting.pop() # today settles this colder day
answer[day] = today - day
waiting.append(today)
return answerNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.