DSAMotivator

Daily Temperatures

Medium·🥞 Stack & Monotonic Stack·Open on LeetCode ↗

For each day, report how many days you must wait for a warmer one, or zero if no warmer day ever comes.

temperatures = [73, 74, 71, 69, 76, 72, 78]step 1/22
73
74
71
69
76
72
78
0
1
2
3
4
5
6
stack
waiting
—

Days still waiting for a warmer one sit on a stack, warmest at the bottom.

1def daily_temperatures(temps):
2    answer = [0] * len(temps)
3    stack = []
4    for i, t in enumerate(temps):
5        while stack and temps[stack[-1]] < t:
6            j = stack.pop()
7            answer[j] = i - j
8        stack.append(i)
9    return answer
Read the 22 steps as text
  1. 1Days still waiting for a warmer one sit on a stack, warmest at the bottom.
  2. 2Day 0 is 73°.
  3. 3Nothing else on the stack is colder than 73°. Day 0 joins the queue.
  4. 4Day 1 is 74°.
  5. 5Day 0 was waiting at 73°. Today is warmer, so its answer is 1 − 0 = 1.
  6. 6Nothing else on the stack is colder than 74°. Day 1 joins the queue.
  7. 7Day 2 is 71°.
  8. 8Nothing else on the stack is colder than 71°. Day 2 joins the queue.
  9. 9Day 3 is 69°.
  10. 10Nothing else on the stack is colder than 69°. Day 3 joins the queue.
  11. 11Day 4 is 76°.
  12. 12Day 3 was waiting at 69°. Today is warmer, so its answer is 4 − 3 = 1.
  13. 13Day 2 was waiting at 71°. Today is warmer, so its answer is 4 − 2 = 2.
  14. 14Day 1 was waiting at 74°. Today is warmer, so its answer is 4 − 1 = 3.
  15. 15Nothing else on the stack is colder than 76°. Day 4 joins the queue.
  16. 16Day 5 is 72°.
  17. 17Nothing else on the stack is colder than 72°. Day 5 joins the queue.
  18. 18Day 6 is 78°.
  19. 19Day 5 was waiting at 72°. Today is warmer, so its answer is 6 − 5 = 1.
  20. 20Day 4 was waiting at 76°. Today is warmer, so its answer is 6 − 4 = 2.
  21. 21Nothing else on the stack is colder than 78°. Day 6 joins the queue.
  22. 22Days still on the stack never warm up. Waits: [1, 3, 2, 1, 2, 1, 0].

The idea

The brute force looks ahead from every day until it finds something warmer — O(n²) when temperatures trend downward for a long stretch.

Turn it around. Instead of each day searching forward for its answer, let each day resolve the days behind it that were waiting. A day is "waiting" if nothing warmer has appeared yet.

Keep those waiting days on a stack. Here is the property that makes it work: the stack is always in decreasing temperature order, because any day that was warmer than the one arriving got resolved and removed. So today only needs to pop from the top while the top is colder — the moment it isn't, everything below is warmer too and none of it can be resolved today.

Every index is pushed once and popped at most once. That's 2n operations total, even though the inner loop looks nested.

The approach

  1. 1Keep a stack of indices whose answer is still unknown, warmest at the bottom.
  2. 2For each day, pop every index on top whose temperature is colder than today's — today is their answer, at a distance of the index difference.
  3. 3Stop popping at the first index that is warmer or equal; it must keep waiting.
  4. 4Push today's index and continue. Anything still on the stack at the end never gets a warmer day and keeps its zero.

Complexity

Time
O(n)
Space
O(n)

Amortized: the while loop can run many times on one day, but each index enters and leaves the stack exactly once across the whole run.

Code

def daily_temperatures(temps):
    answer = [0] * len(temps)
    stack = []
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            answer[j] = i - j
        stack.append(i)
    return answer

What goes wrong

  • •Storing temperatures on the stack instead of indices. The answer is a distance, and you cannot recover it without knowing where the value came from.
  • •Using `<=` in the pop condition. Equal temperatures are not warmer, so an equal day would be resolved with the wrong answer.
  • •Assuming the stack empties. Days on a falling tail never see anything warmer — initialising the answer array to zero is what handles them, silently.