Daily Temperatures

Examples

Input: temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1, 1, 4, 2, 1, 1, 0, 0]

On day 0 (73°), the very next day (74°) is already warmer, so wait 1 day. On day 2 (75°), the next warmer day is day 6 (76°), 4 days later. The last two days never see anything warmer, so they get 0.

Input: temperatures = [30, 40, 50, 60]
Output: [1, 1, 1, 0]

Temperatures keep rising, so every day just waits for the very next one — except the last day, which has nothing after it.

Input: temperatures = [30, 60, 90]
Output: [1, 1, 0]

Constraints

• 1 <= temperatures.length <= 10^5

• 30 <= temperatures[i] <= 100

Approach

The direct approach checks, for every day, each day that follows it until finding one that's warmer — correct, but it means re-scanning forward from every single day.

A better approach keeps a stack of day-indexes whose warmer day hasn't been found yet. Walk through the temperatures once. Whenever the current day's temperature is higher than the temperature at the index sitting on top of the stack, that top day has just found its answer: pop it and record how many days it waited. Keep doing that as long as the top of the stack is beatable, then push today's index — it's now waiting for its own warmer day. Every index is pushed once and popped at most once, so this finishes in a single pass.

Solutions

Brute Force — Scan Forward From Every Day

For each day, look forward day by day until a warmer temperature shows up, and record the gap.

function dailyTemperatures(temperatures) {
  const n = temperatures.length;
  const answer = new Array(n).fill(0);

  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if (temperatures[j] > temperatures[i]) {
        answer[i] = j - i;
        break;
      }
    }
  }

  return answer;
}

Time: O(n²) · Space: O(1) extra, not counting the output

Optimal — Monotonic Stack

Keep a stack of day-indexes that are still waiting for a warmer day. Whenever the current temperature beats the temperature at the index on top of the stack, that day's wait is now resolved.

function dailyTemperatures(temperatures) {
  const n = temperatures.length;
  const answer = new Array(n).fill(0);
  const stack = []; // indexes of days still waiting for a warmer day

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

  return answer;
}

Time: O(n), since each index is pushed and popped at most once · Space: O(n)