Module 08 · Monotonic Stacks and Monotonic Deques

073. Days Until Warmer Temperature

Foundation · Download this solution · All solutions and shared helpers

Problem

For each daily temperature, return how many days must pass before a strictly warmer day. Return zero where no warmer day exists. Temperatures may repeat; output distances rather than temperature values.

Examples

Example 1

warmer_days([73,74,75,71,69,72,76,73])
=> [1, 1, 4, 2, 1, 1, 0, 0]

Each answer measures the distance to the first warmer day.

Example 2

warmer_days([70,70,71])
=> [2, 1, 0]

The equal middle day does not resolve day zero.

Example 3

warmer_days([])
=> []

No days need answers.

Reveal the worked solution and reasoning

Why this mechanism works

The pending-neighbor mechanism is unchanged from next greater element. Store indices because the required output is a distance. A warmer incoming day resolves every cooler day currently exposed at the stack top.

State and boundaries

stack contains unresolved day indices with nonincreasing temperatures. answer[j] becomes i-j when day i resolves day j.

Protocol

Initialize all waits to zero.
For each day pop cooler pending days.
Store the index difference for each pop.
Push the current day.

Visualization

day 0:73 waits for day 1:74 -> 1
day 3:71 waits for day 5:72 -> 2
store indices to measure the wait

Python implementation

def warmer_days(temperatures):
    answer = [0] * len(temperatures)
    stack = []
    for i, value in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < value:
            day = stack.pop()
            answer[day] = i - day
        stack.append(i)
    return answer

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

warmer_days([73,74,75,71,69,72,76,73])

L2 warmer_days: answer = [0] * len(temperatures)
temperatures=[73, 74, 75, 71, 69, 72, 76, 73]; answer=[0, 0, 0, 0, 0, 0, 0, 0]

L3 warmer_days: stack = []
temperatures=[73, 74, 75, 71, 69, 72, 76, 73]; answer=[0, 0, 0, 0, 0, 0, 0, 0]; stack=[]

L4 warmer_days: for i, value in enumerate(temperatures):
temperatures=[73, 74, 75, 71, 69, 72, 76, 73]; answer=[0, 0, 0, 0, 0, 0, 0, 0]; stack=[]; i=0; value=73

L8 warmer_days: stack.append(i)
temperatures=[73, 74, 75, 71, 69, 72, 76, 73]; answer=[0, 0, 0, 0, 0, 0, 0, 0]; stack=[0]; i=0; value=73

L4 warmer_days: for i, value in enumerate(temperatures):
temperatures=[73, 74, 75, 71, 69, 72, 76, 73]; answer=[0, 0, 0, 0, 0, 0, 0, 0]; stack=[0]; i=1; value=74

L6 warmer_days: day = stack.pop()
temperatures=[73, 74, 75, 71, 69, 72, 76, 73]; answer=[0, 0, 0, 0, 0, 0, 0, 0]; stack=[]; i=1; value=74; day=0

L7 warmer_days: answer[day] = i - day
temperatures=[73, 74, 75, 71, 69, 72, 76, 73]; answer=[1, 0, 0, 0, 0, 0, 0, 0]; stack=[]; i=1; value=74; day=0

L8 warmer_days: stack.append(i)
temperatures=[73, 74, 75, 71, 69, 72, 76, 73]; answer=[1, 0, 0, 0, 0, 0, 0, 0]; stack=[1]; i=1; value=74; day=0

... 18 intermediate state changes omitted ...

L7 warmer_days: answer[day] = i - day
temperatures=[73, 74, 75, 71, 69, 72, 76, 73]; answer=[1, 1, 4, 2, 1, 1, 0, 0]; stack=[]; i=6; value=76; day=2

L8 warmer_days: stack.append(i)
temperatures=[73, 74, 75, 71, 69, 72, 76, 73]; answer=[1, 1, 4, 2, 1, 1, 0, 0]; stack=[6]; i=6; value=76; day=2

L4 warmer_days: for i, value in enumerate(temperatures):
temperatures=[73, 74, 75, 71, 69, 72, 76, 73]; answer=[1, 1, 4, 2, 1, 1, 0, 0]; stack=[6]; i=7; value=73; day=2

L8 warmer_days: stack.append(i)
temperatures=[73, 74, 75, 71, 69, 72, 76, 73]; answer=[1, 1, 4, 2, 1, 1, 0, 0]; stack=[6, 7]; i=7; value=73; day=2

Result: [1, 1, 4, 2, 1, 1, 0, 0]. Each answer measures the distance to the first warmer day.

warmer_days([70,70,71])

L2 warmer_days: answer = [0] * len(temperatures)
temperatures=[70, 70, 71]; answer=[0, 0, 0]

L3 warmer_days: stack = []
temperatures=[70, 70, 71]; answer=[0, 0, 0]; stack=[]

L4 warmer_days: for i, value in enumerate(temperatures):
temperatures=[70, 70, 71]; answer=[0, 0, 0]; stack=[]; i=0; value=70

L8 warmer_days: stack.append(i)
temperatures=[70, 70, 71]; answer=[0, 0, 0]; stack=[0]; i=0; value=70

L4 warmer_days: for i, value in enumerate(temperatures):
temperatures=[70, 70, 71]; answer=[0, 0, 0]; stack=[0]; i=1; value=70

L8 warmer_days: stack.append(i)
temperatures=[70, 70, 71]; answer=[0, 0, 0]; stack=[0, 1]; i=1; value=70

L4 warmer_days: for i, value in enumerate(temperatures):
temperatures=[70, 70, 71]; answer=[0, 0, 0]; stack=[0, 1]; i=2; value=71

L6 warmer_days: day = stack.pop()
temperatures=[70, 70, 71]; answer=[0, 0, 0]; stack=[0]; i=2; value=71; day=1

L7 warmer_days: answer[day] = i - day
temperatures=[70, 70, 71]; answer=[0, 1, 0]; stack=[0]; i=2; value=71; day=1

L6 warmer_days: day = stack.pop()
temperatures=[70, 70, 71]; answer=[0, 1, 0]; stack=[]; i=2; value=71; day=0

L7 warmer_days: answer[day] = i - day
temperatures=[70, 70, 71]; answer=[2, 1, 0]; stack=[]; i=2; value=71; day=0

L8 warmer_days: stack.append(i)
temperatures=[70, 70, 71]; answer=[2, 1, 0]; stack=[2]; i=2; value=71; day=0

Result: [2, 1, 0]. The equal middle day does not resolve day zero.

Why the solution is correct

Each pending day has seen no warmer successor before the resolving day. Hence that day gives the minimum waiting distance. Remaining pending days never encounter a warmer successor and correctly keep zero.

Time and space

O(n) time and O(n) space.

Common mistakes

Returning the temperature difference answers a different question. Equal temperatures cannot resolve one another.

Reasoning card

State: stack contains unresolved day indices with nonincreasing temperatures. answer[j] becomes i-j when day i resolves day j.

Invariant: Stack indices wait for their first warmer future day.

Decision to rehearse: Write distance rather than the resolving value.

Finish: Push the current day

Transfer exercise

Require a temperature at least delta warmer. Explain why the simple monotonic-stack pop rule may no longer preserve the same candidate ordering.