For each day, how many days until a warmer temperature?

How to think about it

What the interviewer is really probing here is whether you can recognise “next greater element to the right” hiding inside a story about weather. Brute force is obvious — for each day, scan forward until it gets warmer — and it is O(n²). The question is whether you can see why a single pass is enough, and a monotonic stack is the proof.

The idea fits in one sentence: keep a stack of indices of days that are still waiting for a warmer future, ordered so their temperatures only decrease as you go down. When a new day arrives hotter than the day on top of the stack, that waiting day has just found its answer — pop it, and the gap is simply today's index − its index. Keep popping while the new day still beats the top, then push today. Whatever is left on the stack when you finish never warmed up, so its answer stays 0. Store indices, not temperatures: you need the index both to measure the gap and to write into the answer array.

A worked example

def daily_temperatures(temps):
    n = len(temps)
    answer = [0] * n
    stack = []  # indices, monotonic decreasing by temperature
    for i, t in enumerate(temps):
        while stack and t > temps[stack[-1]]:
            j = stack.pop()
            answer[j] = i - j     # day j finally found a warmer day at i
        stack.append(i)
    return answer

print(daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]))
print(daily_temperatures([30, 40, 50, 60]))      # always rising
print(daily_temperatures([60, 50, 40, 30]))      # always falling
print(daily_temperatures([70, 70, 70]))          # ties never trigger a pop

# Trace the stack to watch the waiting days resolve
def daily_temperatures_verbose(temps):
    answer = [0] * len(temps)
    stack = []
    for i, t in enumerate(temps):
        while stack and t > temps[stack[-1]]:
            j = stack.pop()
            answer[j] = i - j
        stack.append(i)
        print(f"  i={i}, t={t}, stack(indices)={stack}, answer={answer}")
    return answer

print("Trace for [73,74,75,71,69,72,76,73]:")
daily_temperatures_verbose([73, 74, 75, 71, 69, 72, 76, 73])

[1, 1, 4, 2, 1, 1, 0, 0]
[1, 1, 1, 0]
[0, 0, 0, 0]
[0, 0, 0]
Trace for [73,74,75,71,69,72,76,73]:
  i=0, t=73, stack(indices)=[0], answer=[0, 0, 0, 0, 0, 0, 0, 0]
  i=1, t=74, stack(indices)=[1], answer=[1, 0, 0, 0, 0, 0, 0, 0]
  i=2, t=75, stack(indices)=[2], answer=[1, 1, 0, 0, 0, 0, 0, 0]
  i=3, t=71, stack(indices)=[2, 3], answer=[1, 1, 0, 0, 0, 0, 0, 0]
  i=4, t=69, stack(indices)=[2, 3, 4], answer=[1, 1, 0, 0, 0, 0, 0, 0]
  i=5, t=72, stack(indices)=[2, 5], answer=[1, 1, 0, 2, 1, 0, 0, 0]
  i=6, t=76, stack(indices)=[6], answer=[1, 1, 4, 2, 1, 1, 0, 0]
  i=7, t=73, stack(indices)=[6, 7], answer=[1, 1, 4, 2, 1, 1, 0, 0]

Watch the cold spell at i=3,4 pile up on the stack — days 3 and 4 are both waiting. At i=5 the temperature 72 clears day 4 (gap 1) and day 3 (gap 2) in one burst, exactly the “process them together” payoff that beats the nested scan. By i=6 the warm 76 sweeps off everything down to day 2, whose answer of 4 was unknowable until that moment. The two days left on the stack at the end, 6 and 7, keep their 0 — nothing warmer ever came.