Daily Temperatures

Given daily temperatures, return an array where answer[i] is how many days you wait after day i for a strictly warmer day, or 0 if none ever comes. (LC 739)

The obvious answer scans forward from every day, and it is O(n²). The expected answer is the monotonic stack, which is worth knowing by name because it keeps coming back.

The recipe

Say before you type: "I keep a stack of days that are still waiting for a warmer one. Their temperatures only ever go down from bottom to top. When today is warmer than the top, that day's wait is over, so I pop it and record the gap. I keep popping until today is no longer warmer, then push today."

1. Keep a stack of indices (not temperatures) for unresolved days.
2. For each day i: while the stack is non-empty and temps[i] > temps[top], pop top and set answer[top] = i - top.
3. Push i.
4. Whatever is left on the stack never saw a warmer day. Those answers stay 0, which is why the array starts filled with zeros.

The code

function dailyTemperatures(temperatures: number[]): number[] {
  const answer = new Array<number>(temperatures.length).fill(0);
  const stack: number[] = []; // indices of days still waiting

  for (let i = 0; i < temperatures.length; i++) {
    while (stack.length && temperatures[i] > temperatures[stack[stack.length - 1]]) {
      const day = stack.pop()!;
      answer[day] = i - day; // the wait is the index gap
    }
    stack.push(i);
  }

  return answer;
}

Why this shape

The stack is monotonic: from bottom to top the waiting days get colder or stay equal. That is what makes popping correct. If today beats the top of the stack, it may also beat the one below, and so on, but it can never beat something buried under a colder day without beating that colder day first. So a single while loop handles every day that today resolves.

It is O(n) even though there is a loop inside a loop. Each index is pushed once and popped at most once, so the total work across all iterations is at most 2n.

The other answer: scan from the right

When an interviewer asks for a second approach, work backwards and jump instead of walking. For day i, start at i + 1 and hop forward by answer[j] whenever temps[j] is not warmer. Each hop skips days already known not to beat temps[j].

function dailyTemperatures(t: number[]): number[] {
  const n = t.length, answer = new Array<number>(n).fill(0);
  for (let i = n - 2; i >= 0; i--) {
    let j = i + 1;
    while (j < n && t[j] <= t[i]) {
      if (answer[j] === 0) { j = n; break; } // nothing warmer after j: none for i either
      j += answer[j];
    }
    if (j < n) answer[i] = j - i;
  }
  return answer;
}

It uses no stack and reaches the same O(n), but it is harder to explain under pressure. Lead with the stack, offer this one if asked.

Complexity

	Cost	Because
Time	O(n)	Every index is pushed once and popped at most once
Space	O(n)	The stack can hold every day when temperatures only fall

Traps

• Push indices, not temperatures. The answer is a distance, and a temperature cannot give you one.
• Strictly warmer. > is right; >= makes equal days resolve each other and returns the wrong answer for plateaus.
• Forgetting the leftovers need no code. They stay 0 because you pre-filled the array. Do not loop over the stack at the end.
• Starting from the quadratic scan and stopping there. Say it first, so the interviewer knows you saw it, then say what it costs and why a stack is better.

The pattern this trains

A monotonic stack answers "what is the next greater (or smaller) element for each position". It is the same shape in Next Greater Element (496, 503), Online Stock Span (901), Largest Rectangle in Histogram (84) and Trapping Rain Water (42). The trigger phrase is "the next day when..." or "the nearest one to the right that is bigger".