Daily Temperatures

Daily Temperatures is a classic monotonic stack problem. It looks like it needs nested loops, but a single clever pass over the array answers every day in O(n).

The slow way first

The obvious idea: for each day i, scan forward until you hit a warmer day and count the steps. That is two nested loops — O(n²). For a long temperature log it is far too slow, and it redoes the same comparisons over and over.

The question to ask: which earlier days are still waiting, and what do they have in common? The days still waiting are exactly the ones in decreasing temperature order — once a warmer day appears, it resolves the most recent waiters first.

The idea: a monotonic decreasing stack

Keep a stack of indices of days that have not yet seen a warmer day. As we scan left to right, the temperatures of the indices on the stack always decrease from bottom to top.

For each new day i with temperature t: while the day on top of the stack is colder than t, that day has just found its warmer day. Pop it and record answer[j] = i - j. Keep popping until the top is warmer (or the stack is empty), then push i.

Each index is pushed once and popped at most once, so the total work across the whole scan is O(n).

Walk through it

Step through the animation. The top row is temps, the bottom row is the answer being filled in, and the stack label shows the indices still waiting. Watch day 2 (75) sit on the stack while 71, 69, 72 come and go, then finally get resolved when 76 arrives — a wait of 4 days. The last two days never find a warmer day, so they keep their starting value of 0.

Pseudocode

answer = array of zeros, same length as temps
stack = empty   # holds indices of days waiting for a warmer day
for each index i with temperature t in temps:
    while stack is not empty and temps[top of stack] < t:
        j = pop the stack
        answer[j] = i - j        # day j finally got a warmer day
    push i onto the stack
return answer                    # indices left on the stack stay 0

The Python solution

def daily_temperatures(temps):
    answer = [0] * len(temps)
    stack = []  # indices of unresolved days
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            answer[j] = i - j
        stack.append(i)
    return answer

• answer starts all zeros, so any day never resolved correctly stays 0.
• stack holds indices, not temperatures — we need the index to compute the gap i - j and to look up temps[stack[-1]].
• The while loop is the heart of it: one new warm day can resolve several colder waiting days at once.
• answer[j] = i - j is the number of days waited: the warmer day's index minus the waiting day's index.
• We always append(i) after popping, keeping the stack decreasing.

Complexity

Even though there is a while loop inside the for loop, the total number of pops can never exceed the number of pushes (n), so the whole scan is O(n).

When this pattern shows up

Practice