DSA Daily Temperatures

The problem

Daily Temperatures takes a list of daily temperatures and answers, for each day, how many days pass before a warmer day arrives. A day with no warmer day after it answers 0. The 0 is the agreed signal for no warmer day.

The answer list lines up with the input, one wait per day. The cases below are the ones this article uses throughout.

cases = [
    ([73, 74, 75, 71, 69, 72, 76, 73], [1, 1, 4, 2, 1, 1, 0, 0]),
    ([70, 71, 69, 72], [1, 2, 1, 0]),
    ([70, 70], [0, 0]),
    ([65], [0]),
    ([], []),
]
for temps, expected in cases:
    print("temperatures", temps, "-> waits:", expected)

Read one row at a time. In the first row, the 75 waits four days for the 76. The 76 itself never meets a warmer day, so its answer is 0.

Intuition: look ahead day by day

The first idea looks ahead from each day, one day at a time, until a warmer temperature appears. The distance to that day is the answer. The idea is simple and always correct.

The trap is a falling run of temperatures. Each day in the run scans all the way to the end of the list. The scans find nothing, and they are repeated for every day in the run.

temps = [76, 75, 74, 73]
comparisons = 0
answer = []
for i in range(len(temps)):
    wait = 0
    for j in range(i + 1, len(temps)):
        comparisons += 1
        if temps[j] > temps[i]:
            wait = j - i
            break
    answer.append(wait)
print("waits:", answer)
print("comparisons:", comparisons)

Four falling days cost six comparisons and every answer is 0. The work grows with the square of the run length. The stack below removes the rescanning entirely.

Brute force: scan forward from every day

The brute force is the intuition, written as a function. Each day scans forward until a warmer day or the end of the list. A counter records every temperature comparison.

def waits_brute(temps):
    answer = [0] * len(temps)
    comparisons = 0
    for i in range(len(temps)):
        for j in range(i + 1, len(temps)):
            comparisons += 1
            if temps[j] > temps[i]:
                answer[i] = j - i
                break
    return answer, comparisons

answer, comparisons = waits_brute([70, 71, 69, 72])
print("waits:", answer)
print("comparisons:", comparisons)
answer, comparisons = waits_brute([76, 75, 74, 73])
print("falling waits:", answer)
print("falling comparisons:", comparisons)

The rising-and-falling row settles most days quickly. The falling row pays for a full scan per day. A method that remembers the waiting days avoids paying that price twice for the same day.

The optimal solution: a stack of days still waiting

A stack holds the indices of days still waiting for a warmer day, and each new day pops and settles every cooler waiting day beneath it. That one sentence is the whole method.

The wait for a popped day is the gap between the two indices. Storing indices, not temperatures, is what lets the code measure that wait in days. Temperatures alone carry no distances.

The waiting days sit in falling temperature order from bottom to top. A warmer arrival breaks that order from the top down, and each pop restores it.

def daily_temperatures(temps):
    answer = [0] * len(temps)
    stack = []
    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

cases = [
    ([73, 74, 75, 71, 69, 72, 76, 73], [1, 1, 4, 2, 1, 1, 0, 0]),
    ([70, 71, 69, 72], [1, 2, 1, 0]),
    ([70, 70], [0, 0]),
    ([65], [0]),
    ([], []),
]
for temps, expected in cases:
    result = daily_temperatures(temps)
    print("temperatures", temps, "->", result, "expected:", expected, "match:", result == expected)

All five cases pass. Days left on the stack at the end keep their starting answer of 0. No warmer day ever arrived for them.

Walkthrough: [73, 72, 75, 71] day by day

The walk visits one day at a time. The state is the stack of waiting day indices and the answer list so far. Both print after each day is processed.

temps = [73, 72, 75, 71]
answer = [0] * len(temps)
stack = []
for i, t in enumerate(temps):
    while stack and temps[stack[-1]] < t:
        j = stack.pop()
        answer[j] = i - j
    stack.append(i)
    print("day", i, "temp", t, "- waiting:", stack, "answers:", answer)
print("final waits:", answer)

Day 2 brings 75, which settles both waiting days at once. Day 0 waited two days and day 1 waited one. Days 2 and 3 are still on the stack at the end, so their answers stay 0.

Complexity

The brute force makes up to n times n minus 1, divided by 2, comparisons for n days in the worst case, so its time is O(n^2). The stack pushes each day once and pops each day at most once, so its time is O(n).

The brute force stores only the answer list and its counter, so its extra space is O(1) beyond the answer. The stack holds at most one index per day, so its space is O(n).

for n in (4, 8, 16):
    brute = n * (n - 1) // 2
    pushes = n
    print("days", n, "- brute comparisons:", brute, " stack pushes:", pushes)

At 16 days the scan count is 120 against 16 pushes. Each day is pushed once and popped at most once, so the total stack work can never pass twice the day count.

Edge cases and pitfalls

An equal temperature is not a warmer day. The classic mistake is popping on equal temperatures, which settles a waiting day with a day that is no warmer. The pop test must be strictly cooler than the arrival.

Answering with the temperature gap instead of the day gap is a second mistake. The problem asks how many days pass, so the answer comes from the indices, never from subtracting temperatures.

def daily_temperatures(temps):
    answer = [0] * len(temps)
    stack = []
    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

print("equal days:", daily_temperatures([70, 70]))
print("empty list:", daily_temperatures([]))
print("one day:", daily_temperatures([65]))
print("rising days:", daily_temperatures([60, 70, 80]))
print("warmer on the last day:", daily_temperatures([80, 60, 90]))

The rising row answers 1 for each early day, because the very next day is warmer. The last-day row shows a wait of two days measured across an intervening cooler day.