Daily Temperatures#

Problem#

Given a list of daily temperatures, return a new list where each position holds the number of days you have to wait until a warmer temperature. If no warmer day ever comes, put 0 in that position.

Example#

Input [73, 74, 75, 71, 69, 72, 76, 73] gives [1, 1, 4, 2, 1, 1, 0, 0]. From day 0 (73) the next warmer day is day 1, so you wait 1. From day 2 (75) the next warmer day is day 6, so you wait 4.

Brute force#

For each day, scan forward until you find a warmer temperature. That is O(n squared) in the worst case, for example on a strictly decreasing list.

Optimal approach#

Use a monotonic decreasing stack of indices. Walk the list once. For the current day, while the stack is non-empty and today is warmer than the day at the top index, that earlier day has just found its warmer day: pop it and record the index gap. Then push today’s index. Each index is pushed and popped at most once, so the total work is linear.

Solution#

 1def daily_temperatures(temps: list[int]) -> list[int]:
 2    answer = [0] * len(temps)
 3    stack = []  # indices of days awaiting a warmer day
 4    for day, temp in enumerate(temps):
 5        while stack and temp > temps[stack[-1]]:
 6            prev = stack.pop()
 7            answer[prev] = day - prev
 8        stack.append(day)
 9    return answer
10
11
12print(daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]))
13# [1, 1, 4, 2, 1, 1, 0, 0]

Complexity#

• Time: O(n), each index enters and leaves the stack once.
• Space: O(n) for the stack in the worst case.

This is the model monotonic stack problem. Practice more with the 60-day challenge.