Daily Temperatures

Difficulty: Medium

Problem

You get an array temperatures of daily readings. For each day, work out how many days later a strictly warmer day occurs, and return these counts as an array answer. When no later day is warmer, store 0 for that position.

Example

Input: temperatures = [68, 70, 66, 65, 72, 71, 75, 69]
Output: [1, 3, 2, 1, 2, 1, 0, 0]
Explanation: Day 0 (68) gets warmer on day 1 (70), so 1. Day 1 (70) must wait until day 4 (72), so 3. Day 4 (72) waits for day 6 (75), so 2. Day 6 (75) and day 7 (69) never see a warmer day, so they get 0.

Brute-force approach

For each day, scan forward through all remaining days to find the first warmer temperature.

Steps

  1. For each day i from 0 to n-1:
  2. For each future day j from i+1 to n-1:
  3. If temperatures[j] > temperatures[i]: answer[i] = j - i, break
  4. If no warmer day found: answer[i] = 0

Time complexity: O(n²) · Space complexity: O(1)

Trade-offs

  • For each day, may scan all remaining days → O(n²) worst case
  • Very slow for large inputs (n up to 10⁵)
  • Redundant work: rechecks days that were already compared

Optimal approach

Key insight: Days waiting for warmer weather form a decreasing temperature sequence on the stack. A new warmer day resolves all of them at once.

Use a monotonic decreasing stack of indices. When a warmer temperature is found, pop all colder indices and compute the wait time as the index difference.

Steps

  1. Initialize answer array of zeros and an empty stack
  2. For each day i:
  3. While stack not empty AND temperatures[i] > temperatures[stack.top]:
  4. Pop index, set answer[popped] = i - popped
  5. Push i onto the stack
  6. Return answer (remaining stack indices keep 0)

Time complexity: O(n) · Space complexity: O(n)

Pseudocode

function dailyTemperatures(temperatures):
    n = len(temperatures)
    answer = array of n zeros
    stack = []  // stores indices
    
    for i = 0 to n-1:
        while stack not empty and temperatures[i] > temperatures[stack.top]:
            idx = stack.pop()
            answer[idx] = i - idx
        stack.push(i)
    
    return answer

Hints

  • Use a stack to store indices of days waiting for a warmer temperature
  • When you find a warmer day, calculate the difference in indices
  • The stack maintains a monotonic decreasing order of temperatures

Complexity questions

What is the time complexity of scanning forward for each day?

O(n²). For each of n days, we may scan up to n-1 remaining days → O(n²).

Why is the monotonic stack approach O(n)?

Each index is pushed once and popped at most once → total 2n operations. Every index enters the stack once (push) and leaves at most once (pop). Even though we have a while loop, the total pops across all iterations is ≤ n.

What is the worst-case space for the stack?

O(n). In the worst case (strictly decreasing temperatures), all n indices stay on the stack → O(n).

Check your understanding of Daily Temperatures

For temperatures [73, 74, 75, 71, 69, 72, 76, 73], what is the answer for day 0 (73°)?

1: the next day (74°) is warmer. Day 0 is 73°. Day 1 is 74°, which is warmer. So we wait 1 day. We want the FIRST warmer day, not the warmest overall.

For temperatures [73, 74, 75, 71, 69, 72, 76, 73], what is the answer for day 3 (71°)?

2. Day 3 is 71°. The next warmer day is day 5 (72°). Wait = 5 - 3 = 2 days.

If the temperature never gets warmer after day i, what should answer[i] be?

0. If no future day has a warmer temperature, the answer is 0, meaning there are zero days to wait because a warmer day never comes.

Related problems

Keep practising