Problem 13 · Stacks

Daily Temperatures

MediumClassic DSA & systems

01Problem

Given daily temperatures, return for each day how many days until a warmer temperature (0 if none).

02Key insight

Classic next-greater-element: a monotonic decreasing stack of unresolved indices; each new warmer day resolves everything colder on top of the stack.

03Solution

solution.pypython9 lines

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

Try it first.

TimeO(n)

SpaceO(n)

tests.py · 3 passing

tests.pypython3 lines

assert daily_temperatures([73,74,75,71,69,72,76,73]) == [1,1,4,2,1,1,0,0]
assert daily_temperatures([30,60,90]) == [1,1,0]
assert daily_temperatures([90,80]) == [0,0]

04Staff-level follow-up

Why is it O(n) despite the nested loop? Amortised analysis: each index is pushed once and popped at most once, so total work is 2n.