Daily Temperatures (LeetCode 739)
You're given an array of integers temperatures, one reading per day. Build an output array answer where answer[i] counts how many days you'd have to wait, looking only forward from day i, until a strictly warmer day shows up. When no such day ever comes later in the array, answer[i] stays 0.
Worked Examples
temperatures = [73,74,75,71,69,72,76,73][1,1,4,2,1,1,0,0]75 on day 2, the next warmer day is the 76 on day 6, 4 days later. Nothing after the last 76 or 73 is warmer, so they get 0.temperatures = [30,40,50,60][1,1,1,0]temperatures = [30,60,90][1,1,0]30 waits one day for 60, 60 waits one day for 90, and nothing after 90 is warmer.⚖️Formal Constraints & Bounds
1 <= temperatures.length <= 10530 <= temperatures[i] <= 100
Core Insight
Each element is pushed once and popped at most once, guaranteeing strict linear O(N) runtime.
Real-World Scenario & Production Applications
Stock price breakout detection, meteorology temperature spikes, and audio waveform peak envelope analysis.
Subproblems & Recurrence Decomposition3 Phases
Maintain a stack of indices with strictly decreasing temperatures/heights (stack = []).
stack = [] # Invariant: indices with strictly decreasing values
res = [0] * len(temperatures)Step-by-Step Execution Trace Table
Step i | Temp T[i] | Stack Before [indices] | Pops & Resolutions (ans[prev] = curr - prev) | Stack After | answer Array |
|---|---|---|---|---|---|
| 0 | 73 | [] | None (Stack empty) | [0] | [0, 0, 0, 0, 0, 0, 0, 0] |
| 1 | 74 | [0] | 74 > 73 Pop 0, ans[0] = 1 - 0 = 1 | [1] | [1, 0, 0, 0, 0, 0, 0, 0] |
| 2 | 75 | [1] | 75 > 74 Pop 1, ans[1] = 2 - 1 = 1 | [2] | [1, 1, 0, 0, 0, 0, 0, 0] |
| 3 | 71 | [2] | 71 <= 75 No pop | [2, 3] | [1, 1, 0, 0, 0, 0, 0, 0] |
| 4 | 69 | [2, 3] | 69 <= 71 No pop | [2, 3, 4] | [1, 1, 0, 0, 0, 0, 0, 0] |
| 5 | 72 | [2, 3, 4] | 72 > 69 Pop 4, ans[4] = 5-4 = 172 > 71 Pop 3, ans[3] = 5-3 = 272 <= 75 Stop | [2, 5] | [1, 1, 0, 2, 1, 0, 0, 0] |
| 6 | 76 | [2, 5] | 76 > 72 Pop 5, ans[5] = 6-5 = 176 > 75 Pop 2, ans[2] = 6-2 = 4 | [6] | [1, 1, 4, 2, 1, 1, 0, 0] |
| 7 | 73 | [6] | 73 <= 76 No pop | [6, 7] | [1, 1, 4, 2, 1, 1, 0, 0] |
| End | — | [6, 7] | Unresolved indices remain 0 | — | [1, 1, 4, 2, 1, 1, 0, 0] |
| 1 | n = len(temperatures) |
| 2 | answer = [0] * n |
| 3 | stack = [] # indices, temperatures decreasing |
| 4 | for i, temp in enumerate(temperatures): |
| 5 | while stack and temperatures[stack[-1]] < temp: |
| 6 | prev_idx = stack.pop() |
| 7 | answer[prev_idx] = i - prev_idx |
| 8 | stack.append(i) |
| 9 | return answer |
Conceptual Narrative
Checking future days for each day's "next warmer day" is O(N²). A monotonic decreasing stack resolves all days in a single linear pass by storing unresolved cooler days until a warmer day arrives.
🧭 Conceptual Foundation & Pattern Intuition
For each day in an array of temperatures, we want to know how many days we must wait until a warmer temperature arrives. A brute-force nested loop compares each day with all future days , costing time and timing out on . The key observation is that colder days cannot resolve each other:
- If Day 2 is colder than Day 1, Day 2 cannot be Day 1's answer, but both Day 1 and Day 2 are now waiting for some future warmer day.
- A Monotonic Decreasing Stack stores the indices of days that are still waiting for a warmer temperature.
- When we iterate to day with temperature :
- While the stack is non-empty and : day is the very first warmer day for the day at the top of the stack! We pop
prev_idx = stack.pop()and record the waiting duration:answer[prev_idx] = i - prev_idx. - We push index onto the stack.
- While the stack is non-empty and : day is the very first warmer day for the day at the top of the stack! We pop
- Any day remaining on the stack when the loop terminates never found a warmer day, correctly remaining
0.
🎫 The Analogy: The Waiting Room for Outdoor Cafe Seating
Imagine people waiting for outdoor patio seating at a mountain cafe. Customer A arrives on a 60° day and says "Call me when it gets warmer." Customer B arrives on a 55° day and sits next to Customer A. Customer C arrives on a 50° day. The waiting room is ordered from warmest to coldest. Suddenly, an 65° sunny afternoon arrives! The hostess walks into the waiting room: 65° is warmer than Customer C (50°), so C is seated. It's warmer than Customer B (55°), so B is seated. It's warmer than Customer A (60°), so A is seated! One single warm day clears the entire waiting room in one sweep.
🔑 Why It Works
Even though there is a while loop inside a for loop, every index is pushed onto the stack exactly once and popped at most once. Total operations across the entire array are strictly bounded by , guaranteeing amortized linear time.
Storing temperatures instead of indices on stack: Pushing temperature values instead of array indices prevents calculating the distance to the warmer day (
i - prev_idx). Always push indices.Strictly greater vs greater-or-equal popping: The problem specifies a warmer day (strictly higher temperature). Popping when
temperatures[i] >= temperatures[stack[-1]]treats equal temperatures as warmer days, producing false answers.Default zero initialization: Days that never find a warmer day must report 0. Initializing the result array with zeros (
[0] * len(temperatures)) handles un-popped stack indices automatically.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"How many days you'd have to wait, looking only forward from day i, until a strictly warmer day shows up": for each day, the distance to the next greater value on its right.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Decision rule: pop while temperatures[stack[-1]] < temp, because today is the first warmer day for each popped index; an equal temperature does not pop, so the temperatures on stack never increase (equal ones stay).
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Pushing
tempinstead ofi: the answer is a distance written intoanswer[prev_idx], and a temperature gives neither the distance nor the slot.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd use the Next Greater Element stack. I keep a stack of the day indices still waiting for a warmer day. For each day i, while the day on top is colder than today, today is its first warmer day, so I pop it, prev_idx, and write answer[prev_idx] = i - prev_idx; then I push i. The waiting temperatures never increase from bottom to top, so once today fails against the top it would fail against everything below, and each day is answered by the first warmer day to its right. The trap is pushing the temperature instead of the index: I need the index both for the distance and for the slot in answer. Days never answered keep their 0. Every index is pushed and popped at most once, so it is
O(N)time andO(N)space."
Complexity & Mathematical Proof
O(N)
Look at the loop structure: The outer loop for i, temp in enumerate(temperatures): processes each of the N days. Inside, the while loop while stack and temperatures[stack[-1]] < temp: pops cooler days. Although this looks like a nested loop, analyze the element lifecycles: each day index i is pushed onto stack exactly ONCE and popped from stack at most ONCE across the entire run. Total stack pops across all days combined is <= N. Total operations = N (pushes) + N (pops) = 2N = amortized O(N) linear time.
O(N) Auxiliary
Look at memory allocation: The call stack is iterative O(1). Auxiliary memory is used by stack = [], which in the worst-case of strictly decreasing temperatures (e.g., [90, 80, 70, 60]) stores all N indices without resolving. Thus, auxiliary space is bounded by stack capacity O(N).
Derivation Progression
N total element pushes
Every day index i is pushed onto the monotonic stack exactly once in the outer for loop.
≤ N total pops across all days
The inner while loop pops indices when a warmer day is found. Each index is popped at most once.
N pushes + N pops = 2N ⟹ O(N)
Total stack operations is bounded by 2N, yielding strictly amortized O(N) time.
Variable Definitions
Total number of days in the temperature array
Memory Architecture & Bounds
O(1) Iterative loop with zero recursion frames
O(N) Monotonic stack storing up to N day indices in worst-case decreasing order
O(N) Result array storing wait days for each index
Boundary Best / Worst Cases
strictly increasing temperatures (immediate pops).
.
strictly decreasing temperatures (pops at end).
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "number of days you have to wait until a warmer temperature", "next greater element". Naive brute force checks all future days for each index in (TLE on ). A Senior SWE recognizes the Next Greater Element stack: the stack buffers unresolved colder days; the arrival of a warmer day resolves and pops all buffered colder days.
. Amortized time budget is strictly because every day index is pushed and popped at most once.
In a stream, a day's answer is only known once the next warmer reading arrives, possibly never. Downstream consumers must accept late answers, or a cut-off after which waiting days are closed with the default.
Daily Temperatures (LeetCode 739)
You're given an array of integers temperatures, one reading per day. Build an output array answer where answer[i] counts how many days you'd have to wait, looking only forward from day i, until a strictly warmer day shows up. When no such day ever comes later in the array, answer[i] stays 0.
Worked Examples
temperatures = [73,74,75,71,69,72,76,73][1,1,4,2,1,1,0,0]75 on day 2, the next warmer day is the 76 on day 6, 4 days later. Nothing after the last 76 or 73 is warmer, so they get 0.temperatures = [30,40,50,60][1,1,1,0]temperatures = [30,60,90][1,1,0]30 waits one day for 60, 60 waits one day for 90, and nothing after 90 is warmer.⚖️Formal Constraints & Bounds
1 <= temperatures.length <= 10530 <= temperatures[i] <= 100
Core Insight
Each element is pushed once and popped at most once, guaranteeing strict linear O(N) runtime.
Real-World Scenario & Production Applications
Stock price breakout detection, meteorology temperature spikes, and audio waveform peak envelope analysis.
Subproblems & Recurrence Decomposition3 Phases
Maintain a stack of indices with strictly decreasing temperatures/heights (stack = []).
stack = [] # Invariant: indices with strictly decreasing values
res = [0] * len(temperatures)Step-by-Step Execution Trace Table
Step i | Temp T[i] | Stack Before [indices] | Pops & Resolutions (ans[prev] = curr - prev) | Stack After | answer Array |
|---|---|---|---|---|---|
| 0 | 73 | [] | None (Stack empty) | [0] | [0, 0, 0, 0, 0, 0, 0, 0] |
| 1 | 74 | [0] | 74 > 73 Pop 0, ans[0] = 1 - 0 = 1 | [1] | [1, 0, 0, 0, 0, 0, 0, 0] |
| 2 | 75 | [1] | 75 > 74 Pop 1, ans[1] = 2 - 1 = 1 | [2] | [1, 1, 0, 0, 0, 0, 0, 0] |
| 3 | 71 | [2] | 71 <= 75 No pop | [2, 3] | [1, 1, 0, 0, 0, 0, 0, 0] |
| 4 | 69 | [2, 3] | 69 <= 71 No pop | [2, 3, 4] | [1, 1, 0, 0, 0, 0, 0, 0] |
| 5 | 72 | [2, 3, 4] | 72 > 69 Pop 4, ans[4] = 5-4 = 172 > 71 Pop 3, ans[3] = 5-3 = 272 <= 75 Stop | [2, 5] | [1, 1, 0, 2, 1, 0, 0, 0] |
| 6 | 76 | [2, 5] | 76 > 72 Pop 5, ans[5] = 6-5 = 176 > 75 Pop 2, ans[2] = 6-2 = 4 | [6] | [1, 1, 4, 2, 1, 1, 0, 0] |
| 7 | 73 | [6] | 73 <= 76 No pop | [6, 7] | [1, 1, 4, 2, 1, 1, 0, 0] |
| End | — | [6, 7] | Unresolved indices remain 0 | — | [1, 1, 4, 2, 1, 1, 0, 0] |
| 1 | n = len(temperatures) |
| 2 | answer = [0] * n |
| 3 | stack = [] # indices, temperatures decreasing |
| 4 | for i, temp in enumerate(temperatures): |
| 5 | while stack and temperatures[stack[-1]] < temp: |
| 6 | prev_idx = stack.pop() |
| 7 | answer[prev_idx] = i - prev_idx |
| 8 | stack.append(i) |
| 9 | return answer |
Conceptual Narrative
Checking future days for each day's "next warmer day" is O(N²). A monotonic decreasing stack resolves all days in a single linear pass by storing unresolved cooler days until a warmer day arrives.
🧭 Conceptual Foundation & Pattern Intuition
For each day in an array of temperatures, we want to know how many days we must wait until a warmer temperature arrives. A brute-force nested loop compares each day with all future days , costing time and timing out on . The key observation is that colder days cannot resolve each other:
- If Day 2 is colder than Day 1, Day 2 cannot be Day 1's answer, but both Day 1 and Day 2 are now waiting for some future warmer day.
- A Monotonic Decreasing Stack stores the indices of days that are still waiting for a warmer temperature.
- When we iterate to day with temperature :
- While the stack is non-empty and : day is the very first warmer day for the day at the top of the stack! We pop
prev_idx = stack.pop()and record the waiting duration:answer[prev_idx] = i - prev_idx. - We push index onto the stack.
- While the stack is non-empty and : day is the very first warmer day for the day at the top of the stack! We pop
- Any day remaining on the stack when the loop terminates never found a warmer day, correctly remaining
0.
🎫 The Analogy: The Waiting Room for Outdoor Cafe Seating
Imagine people waiting for outdoor patio seating at a mountain cafe. Customer A arrives on a 60° day and says "Call me when it gets warmer." Customer B arrives on a 55° day and sits next to Customer A. Customer C arrives on a 50° day. The waiting room is ordered from warmest to coldest. Suddenly, an 65° sunny afternoon arrives! The hostess walks into the waiting room: 65° is warmer than Customer C (50°), so C is seated. It's warmer than Customer B (55°), so B is seated. It's warmer than Customer A (60°), so A is seated! One single warm day clears the entire waiting room in one sweep.
🔑 Why It Works
Even though there is a while loop inside a for loop, every index is pushed onto the stack exactly once and popped at most once. Total operations across the entire array are strictly bounded by , guaranteeing amortized linear time.
Storing temperatures instead of indices on stack: Pushing temperature values instead of array indices prevents calculating the distance to the warmer day (
i - prev_idx). Always push indices.Strictly greater vs greater-or-equal popping: The problem specifies a warmer day (strictly higher temperature). Popping when
temperatures[i] >= temperatures[stack[-1]]treats equal temperatures as warmer days, producing false answers.Default zero initialization: Days that never find a warmer day must report 0. Initializing the result array with zeros (
[0] * len(temperatures)) handles un-popped stack indices automatically.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"How many days you'd have to wait, looking only forward from day i, until a strictly warmer day shows up": for each day, the distance to the next greater value on its right.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Decision rule: pop while temperatures[stack[-1]] < temp, because today is the first warmer day for each popped index; an equal temperature does not pop, so the temperatures on stack never increase (equal ones stay).
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Pushing
tempinstead ofi: the answer is a distance written intoanswer[prev_idx], and a temperature gives neither the distance nor the slot.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd use the Next Greater Element stack. I keep a stack of the day indices still waiting for a warmer day. For each day i, while the day on top is colder than today, today is its first warmer day, so I pop it, prev_idx, and write answer[prev_idx] = i - prev_idx; then I push i. The waiting temperatures never increase from bottom to top, so once today fails against the top it would fail against everything below, and each day is answered by the first warmer day to its right. The trap is pushing the temperature instead of the index: I need the index both for the distance and for the slot in answer. Days never answered keep their 0. Every index is pushed and popped at most once, so it is
O(N)time andO(N)space."
Complexity & Mathematical Proof
O(N)
Look at the loop structure: The outer loop for i, temp in enumerate(temperatures): processes each of the N days. Inside, the while loop while stack and temperatures[stack[-1]] < temp: pops cooler days. Although this looks like a nested loop, analyze the element lifecycles: each day index i is pushed onto stack exactly ONCE and popped from stack at most ONCE across the entire run. Total stack pops across all days combined is <= N. Total operations = N (pushes) + N (pops) = 2N = amortized O(N) linear time.
O(N) Auxiliary
Look at memory allocation: The call stack is iterative O(1). Auxiliary memory is used by stack = [], which in the worst-case of strictly decreasing temperatures (e.g., [90, 80, 70, 60]) stores all N indices without resolving. Thus, auxiliary space is bounded by stack capacity O(N).
Derivation Progression
N total element pushes
Every day index i is pushed onto the monotonic stack exactly once in the outer for loop.
≤ N total pops across all days
The inner while loop pops indices when a warmer day is found. Each index is popped at most once.
N pushes + N pops = 2N ⟹ O(N)
Total stack operations is bounded by 2N, yielding strictly amortized O(N) time.
Variable Definitions
Total number of days in the temperature array
Memory Architecture & Bounds
O(1) Iterative loop with zero recursion frames
O(N) Monotonic stack storing up to N day indices in worst-case decreasing order
O(N) Result array storing wait days for each index
Boundary Best / Worst Cases
strictly increasing temperatures (immediate pops).
.
strictly decreasing temperatures (pops at end).
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "number of days you have to wait until a warmer temperature", "next greater element". Naive brute force checks all future days for each index in (TLE on ). A Senior SWE recognizes the Next Greater Element stack: the stack buffers unresolved colder days; the arrival of a warmer day resolves and pops all buffered colder days.
. Amortized time budget is strictly because every day index is pushed and popped at most once.
In a stream, a day's answer is only known once the next warmer reading arrives, possibly never. Downstream consumers must accept late answers, or a cut-off after which waiting days are closed with the default.