Marauder Bot

Problem

Given a list of daily temperatures, determine for every day how many days must pass before a strictly warmer day occurs later in the list. If no warmer day ever follows, the answer for that day is 0.

Example. For temperatures [73, 74, 75, 71, 69, 72, 76, 73], the answer is [1, 1, 4, 2, 1, 1, 0, 0]: day 0 (73°) waits just 1 day to reach 74°, while day 2 (75°) waits 4 days to reach 76°.

Key idea

Scanning forward from each day to find its next warmer day works but costs O(n²) in the worst case, such as strictly decreasing temperatures. The improvement comes from processing days left to right while keeping a backlog of days still waiting for an answer, resolving several at once whenever a sufficiently warm day arrives.

Maintain a stack of day indices whose warmer day has not yet been found, kept so temperatures decrease from bottom to top. When the current day is warmer than the top of the stack, that day's wait is over: pop it, and its answer is the gap between its index and the current one. Keep comparing against the new top, since the current day may resolve several backlogged days at once. Once no more pops apply, push the current index and move on. Any index left on the stack at the end never found a warmer day.

Solution

function dailyTemperatures(temperatures: number[]): number[] {
  const answer = new Array<number>(temperatures.length).fill(0);
  const stack: number[] = [];

  for (let i = 0; i < temperatures.length; i++) {
    // Resolve every backlogged day that today's temperature beats.
    while (stack.length > 0 && temperatures[i] > temperatures[stack[stack.length - 1]]) {
      const dayIndex = stack.pop()!;
      answer[dayIndex] = i - dayIndex; // Distance between the waiting day and today.
    }
    stack.push(i); // Stack stays in decreasing temperature order from bottom to top.
  }

  return answer;
}

Complexity

Time: O(n). Each index is pushed and popped at most once, even though the inner comparison looks like a nested loop.
Space: O(n). The stack can hold every index in the worst case, such as strictly decreasing temperatures.

Watch out for

Store indices on the stack, not temperatures, since the answer needs the distance between days.
Initialize answers to 0 so unresolved days need no extra handling.
The comparison must be strictly "warmer than," not "at least as warm."

Pattern

This is the monotonic stack pattern for "next greater element" problems. The same structure reappears in this library for counting car fleets and computing the largest rectangle in a histogram.

Daily Temperatures