739. Daily Temperatures

At a Glance

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

Problem (one-liner)

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

Recognition Cues

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

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

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;
}

Walkthrough

temperatures = [73,74,75,71,69,72,76,73]

When 72 at index 5 arrives, it resolves waits for indices still waiting with cooler tops.

Invariant: stack indices have decreasing temperatures; warmer day pops all cooler unresolved days.

Edge Cases

• Strictly decreasing sequence → all zeros
• All equal temperatures → zeros
• Last day always implies no warmer future from itself

Pitfalls

• Using values stack without indices (need distance)
• Popping after forgetting to assign answer for popped index

Similar Problems

• 853. Car Fleet — ordering and collision resolution over time-like axes.
• 020. Valid Parentheses — stack workflow familiarity.
• 394. Decode String — index/stack disciplined traversal on structured input.

Variants

• Circular array — duplicate scan or modulo indexing.
• Next greater-or-equal vs strictly greater.

Mind-Map Tags

#monotonic-stack #next-greater #indices #waiting-days #linear-time