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. (The walkthrough and animations below use a different list, [73, 74, 75, 71, 69, 72, 76, 73], whose answer is [1, 1, 4, 2, 1, 1, 0, 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 sequence on the stack that never goes up from bottom to top (equal temperatures stay, since > is strict). A new warmer day resolves all of the colder ones at once.

Use a monotonic stack of indices (temperatures never go up from bottom to top). 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

// Order matters: test 'stack not empty' first, an empty stack has no top.
// Use > (not >=): an equal temperature is not warmer, so that day stays on the stack.

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
  • First warmer day, not the warmest later day: day 0 of [73, 74, 75, ...] waits 1 day for the 74, not 2 days for the 75
  • The stack of waiting days never goes up from bottom to top (equal temperatures stay on it, because only a strictly warmer day pops)
  • What if we popped only one day per arrival? On [68, 70, 66, 65, 72, 71, 75, 69] you would get [1, 0, 0, 1, 0, 1, 0, 0], so keep popping while the new day is warmer than the top

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). The answer array holds n numbers too, so the total space is 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