Daily Temperatures

You're given an array temperatures where temperatures[i] is the temperature on day i.

Return an array answer of the same length where answer[i] is the number of days after day i until a strictly warmer day. If no later day is warmer, answer[i] is 0.

Each day is asking "what is the next greater element to my right?" That phrase is the cue for a monotonic stack.

Walk left to right and keep a stack of the indices of days that are still waiting for a warmer day. Their temperatures are always in non-increasing order from bottom to top, because any day warmer than the top would have already resolved it. When today is warmer than the day on top of the stack, today is that day's answer: pop it and record today - index. Keep popping while today beats the top, then push today.

Each index is pushed once and popped at most once, so the whole pass is linear even though there is a loop inside a loop.

def daily_temperatures(temperatures: list[int]) -> list[int]:
    answer = [0] * len(temperatures)
    stack: list[int] = []  # indices still waiting for a warmer day
    for i, temp in enumerate(temperatures):
        while stack and temp > temperatures[stack[-1]]:
            j = stack.pop()
            answer[j] = i - j
        stack.append(i)
    return answer

function dailyTemperatures(temperatures) {
  const answer = new Array(temperatures.length).fill(0);
  const stack = []; // indices still waiting for a warmer day
  for (let i = 0; i < temperatures.length; i++) {
    while (stack.length && temperatures[i] > temperatures[stack[stack.length - 1]]) {
      const j = stack.pop();
      answer[j] = i - j;
    }
    stack.push(i);
  }
  return answer;
}

Name the pattern explicitly: "this is next greater element, so I'll use a monotonic stack." Then state the invariant (the stack holds unresolved days with non-increasing temperatures) and the amortized argument (every index is pushed and popped at most once). Those two sentences are what interviewers want to hear.

Trace the example by hand for three or four steps, showing what is on the stack, and call out the equal-temperature case before you finish.