Daily Temperatures
Problem Description
For each day's temperature, return how many days until a strictly warmer temperature occurs. Use 0 if none occurs later.
Example: [30, 40, 35, 50] returns [1, 2, 1, 0]. Equal temperatures do not count as warmer.
Think about: A day can be resolved as soon as a warmer future day is found.
Worked solution Open when you’re ready to compare your approach
Approach
Maintain a stack of unresolved indices whose temperatures are in nonincreasing order. A new warmer temperature resolves indices from the top until the order is restored.
def days_until_warmer(temperatures: list[int]) -> list[int]:
result = [0] * len(temperatures)
waiting = []
for today, temperature in enumerate(temperatures):
while waiting and temperatures[waiting[-1]] < temperature:
earlier = waiting.pop()
result[earlier] = today - earlier
waiting.append(today)
return result
Each index is pushed once and popped at most once, yielding O(n) time and O(n) space. The nested while loop does not make the total time quadratic.
Check yourself: Why does the stack keep indices rather than temperatures alone?
Worked trace
For [30, 40, 35, 50], day 0 waits on the stack. Day 1 is warmer, so resolve day 0 with a wait of 1; day 1 then waits. Day 2 is cooler than day 1, so both indices remain. Day 3 is warmer than days 2 and 1: their waits are 1 and 2. Day 3 has no later warmer day, leaving its answer at the initial 0.
Why it works and what to watch for
The stack holds indices whose next warmer day is still unknown, with temperatures in nonincreasing order from bottom to top. When a new temperature exceeds the top, it is the first later day that can resolve that index: any earlier processed day was not warm enough. Each index is pushed once and popped at most once, so the total work is O(n), even though a single iteration may pop several indices. Use a strict > comparison; an equal temperature is not warmer. Repeated temperatures remain on the stack until a truly warmer day appears. A straightforward scan forward from every day is easier to write but can take O(n²) time.
Step 4 of 7 · Core interview practice
Put this step into practice.
Explain why a nested while loop can still give linear total time.
Enable JavaScript to save progress. You can still continue through the path.
