Daily Temperatures

Difficulty: Medium

Problem

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0.

Example

Input: temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1, 1, 4, 2, 1, 1, 0, 0]
Explanation: Day 0 (73°): next warmer is day 1 (74°) → wait 1 day. Day 2 (75°): next warmer is day 6 (76°) → wait 4 days. Last two days have no warmer future day → 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)