739. Daily Temperatures

Quick Identifier

Topic: stack
Pattern: Monotonic Stack
Difficulty: Medium
Companies: Amazon, Google, Meta, Bloomberg, Microsoft
Frequency: Very High
LeetCode: 739

Quick Sights

Time Complexity: See optimal approach. from the optimal approach.
Space Complexity: See optimal approach. from the optimal approach.
Core Mechanism: Given daily temperatures, return an array where each position holds how many days until a warmer temperature; 0 if none future.

Concept Explanation

Given daily temperatures, return an array where each position holds how many days until a warmer temperature; 0 if none future.

The key is to state the invariant before coding: what part of the input is already settled, what state is still unresolved, and what single operation makes progress without losing correctness.

Recognition cues:

"Next greater element" with distance, not value
Stack of indices with decreasing temperatures while scanning
Monotonic decreasing stack of temps / indices

Study Pattern (SDE3+)

0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Loading diagram…

Approaches

Brute force — nested loops — O(n²).
Better — monotonic stack — O(n) time / O(n) space typical.
Optimal — single pass index stack — answer filled when warmer day pops colder tops.

Optimal Solution

Go

func dailyTemperatures(temperatures []int) []int {
	n := len(temperatures)
	answer := make([]int, n)
	stack := make([]int, 0, n)
	for day := 0; day < n; day++ {
		for len(stack) > 0 && temperatures[day] > temperatures[stack[len(stack)-1]] {
			prior := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			answer[prior] = day - prior
		}
		stack = append(stack, day)
	}
	return answer
}

JavaScript

function dailyTemperatures(temperatures) {
	const answer = new Array(temperatures.length).fill(0);
	const stack = [];
	for (let day = 0; day < temperatures.length; day++) {
		while (
			stack.length > 0 &&
			temperatures[day] > temperatures[stack.at(-1)]
		) {
			const priorDay = stack.pop();
			answer[priorDay] = day - priorDay;
		}
		stack.push(day);
	}
	return answer;
}