LeetCode · #739

Daily Temperatures Solution

Given daily temperatures, return an array where answer[i] is the number of days until a warmer temperature. If no warmer day exists, answer[i] = 0.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #739

🏗️

Pattern

Monotonic Stack — next greater element

Given an array of integers temperatures, return an array answer such that answer[i] is the number of days you have to wait after the i-th day to get a warmer temperature. If there is no future day with a warmer temperature, set answer[i] = 0.

Example

 Input: temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1, 1, 4, 2, 1, 1, 0, 0]
// Day 0 (73°): next warmer is day 1 (74°) → 1 // Day 2 (75°): next warmer is day 6 (76°) → 4 days 

Constraints

• 1 ≤ temperatures.length ≤ 10⁵ • 30 ≤ temperatures[i] ≤ 100

Section Two · Approach 1

Brute Force — O(n²)

For each day, scan rightward to find the first warmer day. Record the distance.

Problem: O(n) scan per day → O(n²) total. A monotonic decreasing stack resolves all "waiting" days in one pass — each day is pushed once and popped once for O(n).

Java — Brute Force

 class Solution {
public int[] dailyTemperatures(int[] temps) {
int[] answer = new int[temps.length];
for (int i = 0; i < temps.length; i++)
for (int j = i + 1; j < temps.length; j++)
if (temps[j] > temps[i]) { answer[i] = j - i; break; }
return answer;
    }
}

Python — Brute Force

 class Solution:
def dailyTemperatures(self, temps: list[int]) -> list[int]:
        answer = [0] * len(temps)
for i in range(len(temps)):
for j in range(i + 1, len(temps)):
if temps[j] > temps[i]:
                    answer[i] = j - i
break return answer

Metric	Value
Time	O(n²)
Space	O(1) — excluding output

Section Three · Approach 2

Monotonic Stack — O(n)

Maintain a stack of indices representing days waiting for a warmer temperature. The stack is in decreasing temperature order. When a new day is warmer than the stack's top, pop and resolve — the wait is current_index − popped_index.

💡 Mental model: Imagine a queue of people waiting for the sun to come out. When a warmer day arrives, everyone in the queue who was waiting for at least this much warmth steps out and records how long they waited. The remaining people (who need even more warmth) keep waiting. New arrivals join the back.

Algorithm

Step 1: Create an empty stack (stores indices, not temperatures).
Step 2: For each day i:
Step 3: While stack is non-empty AND temps[i] > temps[stack.peek()]: pop index j. Set answer[j] = i − j.
Step 4: Push i onto the stack.
Step 5: Remaining stack indices get 0 (no warmer day) — already initialized.

🎯 Monotonic stack pattern:

Any "next greater element" or "next smaller element" problem → monotonic stack.
The stack maintains a decreasing (for next-greater) or increasing (for next-smaller) order.
When an element breaks the monotonicity, all violated elements get their answer.
Each element is pushed/popped exactly once → O(n).

Section Four · Trace

Visual Walkthrough

Trace through temps = [73, 74, 75, 71, 69, 72, 76, 73]:

Monotonic Decreasing Stack — pop when warmer day found

Section Five · Implementation

Code — Java & Python

Java — Monotonic Stack

 import java.util.Stack;
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int[] answer = new int[temperatures.length];
Stack<Integer> stack = new Stack<>(); // indices for (int i = 0; i < temperatures.length; i++) {
while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
int j = stack.pop();
                answer[j] = i - j;
            }
            stack.push(i);
        }
return answer; // remaining indices default to 0
}
}

Python — Monotonic Stack

 class Solution:
def dailyTemperatures(self, temperatures: list[int]) -> list[int]:
        answer = [0] * len(temperatures)
        stack = [] # indices for i, temp in enumerate(temperatures):
while stack and temp > temperatures[stack[-1]]:
                j = stack.pop()
                answer[j] = i - j
            stack.append(i)
return answer

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Brute Force	O(n²)	O(1)	Scan right for each day
Monotonic Stack ← optimal	O(n)	O(n)	Each index pushed/popped once. Stack holds waiting days.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Decreasing	`[76, 75, 74, 73]`	No warmer days → all zeros. Stack grows to size n.
Increasing	`[73, 74, 75, 76]`	Every day pops immediately → all 1s except last (0).
All same	`[70, 70, 70]`	Equal is NOT warmer → all zeros.
Single day	`[73]`	No future days → [0].
Warmer at end	`[73, 71, 69, 76]`	Day 6 resolves all waiting days at once — multiple pops.

⚠ Common Mistake: Using >= instead of > in the comparison. The problem asks for a strictly warmer day. If you pop on equal temperatures, you'll report a day that isn't actually warmer. Always use strict >.

← Back to Stack problems

LearningTree

LC 739 · Daily Temperatures — Solution & Explanation | DSA Guide