Daily Temperatures With a Monotonic Stack

Daily Temperatures is LeetCode 739, rated Medium. Given a list of daily temperatures, answer[i] is how many days you wait until a strictly warmer day. If none exists, the answer is 0. It looks like a nested scan. The interview is whether you notice each day is resolved at most once.

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

73 waits one day for 74. 75 waits four days for 76. 76 never sees a warmer day.

The stack

Walk left to right. Keep a stack of indexes whose warmer day is still unknown. The temperatures at those indexes stay in decreasing order: the top of the stack is the most recent, coolest unresolved day.

When today's temperature is strictly greater than the temperature at the top, that earlier day has found its answer. The distance is today's index minus that index. Pop, write the distance, and keep popping while today is still warmer than the new top. Then push today. Today is now the coolest unresolved day, which restores the decreasing order.

def daily_temperatures(temperatures: list[int]) -> list[int]:
    answer = [0] * len(temperatures)
    stack: list[int] = []  # indexes, temperatures decrease toward the top

    for i, temp in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < temp:
            prev = stack.pop()
            answer[prev] = i - prev
        stack.append(i)

    return answer

Days still on the stack at the end never found a warmer day. They stay 0, which is what the array was initialized to. You do not need a second pass.

Why the inequality is strict

The problem asks for a warmer day, not an equal one. The while condition uses <. If today equals the top, today does not resolve it. Push today on top. A later warmer day can still resolve both, and the closer one is on top, so it gets the smaller distance. Using <= would treat an equal day as warmer and produce a wrong distance.

Complexity

Each index is pushed once and popped at most once, so the while loop across the whole array is O(n), not O(n^2). The stack holds indexes, so the extra space is O(n). A strictly increasing input pops on every step and every answer is 1. A strictly decreasing input never pops, the stack grows to n, and the answer is all zeros.

The brute force is for each day, scan forward until a warmer one. That is O(n^2) and it repeats work: a later day re-scans temperatures an earlier day already ruled out. The stack remembers exactly those unresolved days.

Follow-ups

Next Greater Element to the right is this loop writing the value instead of the distance. The circular version is the same stack, with the array conceptually walked twice, and you still push each index once. Stock span asks for the distance back to the previous greater day, so the stack is walked from the other direction and you pop smaller-or-equal days before computing the span.

Valid Parentheses is the other stack problem interviewers open with: there the stack stores unmatched brackets, here it stores unmatched days. More of these sit in the Technical Interview category.