Daily temperatures

Medium TimeO(n) SpaceO(n)

Given temps, the temperature on each day, return for each day how many days must pass before a strictly warmer one, and 0 where no warmer day follows. The answer is a distance in days rather than a temperature, and the same temperature does not end the wait — so the last day always answers 0.

Examples

Example 1

Input
temps = [73, 74, 75, 71, 69, 72, 76, 73]
Output
[1,1,4,2,1,1,0,0]
Day 2's 75 waits 4 days for the 76, and the last two days never see anything warmer.

Example 2

Input
temps = [30, 30, 31]
Output
[2,1,0]
Day 1 repeats day 0's 30, which does not end its wait: it takes until day 2, 2 days on.

The Code

function dailyTemperatures(temps) {
  const answer = new Array(temps.length).fill(0);
  const stack = [];
  for (let i = 0; i < temps.length; i++) {
    while (stack.length > 0 && temps[i] > temps[stack[stack.length - 1]]) {
      const day = stack.pop();
      answer[day] = i - day;
    }
    stack.push(i);
  }
  return answer;
}
dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73]);
Done
Step through dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73]) call by call

More like this

All stacks & queues examples (8) →