Daily Temperatures

You'll use a monotonic stack. Instead of each day searching ahead, each new day answers the earlier days still waiting. The waiting days always line up in a way that makes this cheap. You need list indexes and a stack's push and pop. Related chapter: monotonic stack.

1. The problem

You get a list of daily temperatures. For each day, return how many days until the first strictly warmer day. Use 0 if no warmer day comes. Don't change the input. An empty list returns []. This is Daily Temperatures (LC 739).

"Strictly" and "first" both matter. An equal temperature does not count, and a later, even warmer day does not replace the first one.

2. A correct baseline

For each day, scan forward until a warmer day appears.

def baseline(temperatures):
    answer = [0] * len(temperatures)
    for day in range(len(temperatures)):
        for later in range(day + 1, len(temperatures)):
            if temperatures[later] > temperatures[day]:
                answer[day] = later - day
                break
    return answer

assert baseline([75, 70, 72, 76]) == [3, 1, 1, 0]
assert baseline([70, 70, 71]) == [2, 1, 0]
assert baseline([80, 70, 60]) == [0, 0, 0]
assert baseline([]) == []

On a list that never warms up, no scan stops early. So the brute force makes n(n − 1) / 2 comparisons. That's O(n²) time: the work grows with the square of the number of days. With LeetCode's 100,000 days, it's about five billion.

The bottleneck. The scans overlap. Day 0 reads days 1, 2, 3, and so on. Then day 1 reads days 2, 3, and so on, again. Each scan learns about the days ahead, then throws it away.

3. The observation

Turn the search around. Walk forward once. When a new day arrives, ask which earlier days it answers. A day gets its answer from the first strictly warmer day after it. Until then, it's pending.

Take [75, 70, 72]. After day 1, both 75 and 70 are pending. Then 72 arrives. It answers 70, the newest pending day. It doesn't answer 75, and it can't answer anything older either.

Why does that always happen? Suppose day a comes before day b, and both are pending. If b were warmer than a, it would already have answered a. So:

Pending days, from oldest to newest, have temperatures that never increase.

That's what makes it cheap. The coolest pending days are the newest ones. When today arrives, compare it with the newest pending day:

• If today is warmer, today is that day's answer. Remove it, and compare with the next newest.
• If not, stop. Every older pending day is at least as warm, so today answers none of them.

Adding and removing at the same end is a stack. Store indexes, not temperatures, because the answer is a distance. This is called a monotonic stack because its temperatures only go one way: they never rise from bottom to top.

This works because a day, once answered, never matters again.

4. The solution and a trace

class Solution:
    def dailyTemperatures(self, temperatures: list[int]) -> list[int]:
        """Return waits for strictly warmer days, without modifying input."""
        answer = [0] * len(temperatures)
        pending = []  # Unresolved indexes; temperatures never increase bottom to top.
        for today, temperature in enumerate(temperatures):
            while pending and temperature > temperatures[pending[-1]]:
                earlier = pending.pop()
                answer[earlier] = today - earlier
            pending.append(today)
        return answer

solve = Solution().dailyTemperatures
assert solve([75, 70, 72, 76]) == [3, 1, 1, 0]
assert solve([70, 70, 71]) == [2, 1, 0]
assert solve([80, 70, 60]) == [0, 0, 0]
assert solve([]) == []
assert solve([72, 70, 70, 71, 75, 69]) == [4, 2, 1, 1, 0, 0]

Trace [72, 70, 70, 71, 75, 69], which has an equal pair, one day resolving several, and days left over:

Days 4 and 5 are still pending at the end. No warmer day came, so their answers stay 0.

5. Why it works

What stays true. Before day t, pending holds exactly the earlier days that haven't seen a warmer day yet, oldest first. Their temperatures never rise from bottom to top. It starts true, with an empty stack, and each step keeps it true.

Each answer is right. When day t pops day d, today is warmer than d. And d was still pending, so no day between them was warmer. So t is the first warmer day, and answer[d] = t − d.

No day is answered late. The loop stops at the first pending day that today isn't warmer than. Every day below it is at least as warm, so today isn't warmer than those either. So every day today should answer has been popped. Pushing today keeps the order, because the day below it is at least as warm.

Leftovers are right. A day still pending at the end has no warmer day after it, so 0 is its answer.

6. Cost, edge cases, and failure

Cost. The while loop looks nested, but count across the whole run. Each index is pushed once and popped at most once. Each day makes at most one comparison that doesn't pop. So the total is O(n) time, growing in step with the number of days. Extra space is O(n), because a list that never warms up leaves every day pending.

Edge cases. An empty list gives []. All-equal temperatures give all zeros, since equal isn't warmer. A list that warms every day gives all ones except the last, and the stack never holds more than one index.

Where it fails. The comparison decides everything. With >=, an equal day wrongly answers an earlier one:

class ResolveOnEqual:  # deliberately wrong: treats an equal day as warmer
    def dailyTemperatures(self, temperatures):
        answer, pending = [0] * len(temperatures), []
        for today, temperature in enumerate(temperatures):
            while pending and temperature >= temperatures[pending[-1]]:
                earlier = pending.pop()
                answer[earlier] = today - earlier
            pending.append(today)
        return answer

assert ResolveOnEqual().dailyTemperatures([70, 70, 71]) == [1, 1, 0]  # wrong: day 0 waits 2
assert solve([70, 70, 71]) == [2, 1, 0]

Replacing while with if fails differently: day 3 in the trace would answer day 2 but leave day 1 waiting. And a stack can't handle days that expire, as in "the warmest of the last k days". That needs removing from the old end too, with a monotonic deque. See sliding window maximum.

import random

rng = random.Random(739)
for _ in range(2000):
    temperatures = [rng.randint(30, 36) for _ in range(rng.randint(0, 12))]
    assert solve(temperatures) == baseline(temperatures), temperatures