Daily Temperatures

1. Define the problem

Given an array of daily temperatures, return an array where each position holds the number of days you would have to wait until a warmer temperature. If there is no future day with a warmer temperature, put 0 for that day instead. Walk the days once with a monotonic stack of day-indices still waiting for a warmer day — as soon as a warmer temperature shows up, it resolves every colder day still on the stack.

Constraints

1 ≤ temperatures.length ≤ 10⁵
30 ≤ temperatures_i ≤ 100

Example

Inputtemperatures = [73, 74, 75, 71, 69, 72, 76, 73]

Output[1, 1, 4, 2, 1, 1, 0, 0]

Explanation Day 0 (73) waits 1 day for 74. Day 2 (75) waits 4 days for 76. Day 6 (76) and day 7 (73) never see anything warmer, so both are 0.

2. Visualize the solution

Resolve a stack of days still waiting for warmth

073

174

275

371

469

572

676

773

Statuspush

Day 0 (73): stack empty, push day 0.

What happens in this step

i = 0, temp = 73
stack = [] → push 0
stack = [0]
result = [0, 0, 0, 0, 0, 0, 0, 0]

Step 1 of 6

Steps to visualize

Walk the temperatures from left to right, one day at a time.
While today's temperature is warmer than the day on top of the stack, pop that day and record how many days it waited.
Push the current day onto the stack, since its own warmer day has not shown up yet.
Any day still on the stack at the end never gets a warmer day, so it stays 0.

3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Resolve a stack of days still waiting for warmth

073

174

275

371

469

572

676

773

Statuspush

Day 0 (73): stack empty, push day 0.

What happens in this step

i = 0, temp = 73
stack = [] → push 0
stack = [0]
result = [0, 0, 0, 0, 0, 0, 0, 0]

Step 1 of 6

4. Solution

Solution

solution.tsTypeScript

function dailyTemperatures(temperatures) {
  const n = temperatures.length;
  const result = new Array(n).fill(0);
  const stack = [];

  for (let i = 0; i < n; i++) {
    while (stack.length > 0 && temperatures[stack[stack.length - 1]] < temperatures[i]) {
      const top = stack.pop();
      result[top] = i - top;
    }

    stack.push(i);
  }

  return result;
}

Time: O(n)
Space: O(n)

5. Test cases

Test cases

Input	Expected	Covers
`temperatures = [73, 74, 75, 71, 69, 72, 76, 73]`	`[1, 1, 4, 2, 1, 1, 0, 0]`	example from the docstring
`temperatures = [30]`	`[0]`	smallest valid input: a single day never finds warmth
`temperatures = [70, 69, 68]`	`[0, 0, 0]`	temperatures only ever get colder, so nothing waits for warmth
`temperatures = [68, 69, 70]`	`[1, 1, 0]`	temperatures only ever get warmer, so every day but the last waits 1 day
`temperatures = [70, 70, 70]`	`[0, 0, 0]`	equal temperatures never count as strictly warmer
`temperatures = [73, 72, 73]`	`[0, 1, 0]`	a dip and recovery that resolves only the middle day

Daily Temperatures