Daily Temperatures

The idea

For each day I want the number of days until a warmer one. The brute thing is to look forward from every day until I find something hotter. The waste is obvious: I keep rescanning the same colder days over and over.

Flip it around. When a warmer day shows up, it resolves all the earlier days that were waiting for exactly this. So instead of looking forward, I hold onto unresolved days and let a future day clear them out.

Brute force, then the cut

The naive version is two loops: for each i, walk right until temps[j] > temps[i]. That's O(n²), and on a strictly decreasing array it hits the worst case every time.

The cut is a stack of indices whose answer is still open, kept so their temperatures are decreasing from bottom to top. Each new day pops every index on top that it beats, and the answer for a popped index is current_index - popped_index. Anything colder than the current day stays on the stack, waiting.

def daily_temperatures(temperatures: list[int]) -> list[int]:
    answer = [0] * len(temperatures)
    stack: list[int] = []  # indices, decreasing temperature
 
    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

Why it's linear

Each index gets pushed once and popped at most once, so the inner while does O(n) total work across the whole run, not O(n) per day. Days still on the stack at the end never see a warmer day, and their slots stay 0 from the initial fill. O(n) time, O(n) space for the stack.