# LeetCode 739: Daily Temperatures, Explained Visually

> The brute force works, but at 100,000 days it is about 5 billion comparisons. A stack of the days still waiting does it in O(n).

Medium · monotonic stack. Page with the frames from the video: https://www.tmread.me/leetcode/739

## The problem

Given a list of daily `temperatures`, return how many days you wait after each day for a warmer one, or 0 if no warmer day comes. For `[73,74,75,71,69,72,76,73]` the answer is `[1,1,4,2,1,1,0,0]`.

## See it

*Frame from the video: Example 1 as thermometers, one per day. Every answer starts unknown.*

*Frame from the video: The finished answer, [1,1,4,2,1,1,0,0]: days 6 and 7 never see a warmer day, so they stay 0.*

*Frame from the video: Brute force scans forward from every day. Flat temperatures are its worst case: about 5 billion comparisons at 100,000 days.*

*Frame from the video: The days still waiting form a stack that never gets warmer toward the top, a monotonic stack.*

*Frame from the video: Day 5 (72) checks the top of the stack, where 75, 71 and 69 are still waiting.*

*Frame from the video: The stack solution from the video, the same code as below.*

*Frame from the video: The trade: brute force is O(n²) time and O(1) space; the stack is O(n) time and O(n) space.*

## The code

### Python

```python
def dailyTemperatures(temps):
    answer = [0] * len(temps)
    stack = []  # waiting indices

    for i in range(len(temps)):
        while (stack and temps[i]
              > temps[stack[-1]]):
            j = stack.pop()
            answer[j] = i - j
        stack.append(i)

    return answer
```

### TypeScript

```ts
function dailyTemperatures(temps: number[]): number[] {
  const answer: number[] = new Array(temps.length).fill(0);
  const stack: number[] = []; // waiting indices

  for (let i = 0; i < temps.length; i++) {
    while (stack.length > 0 && temps[i]
           > temps[stack[stack.length - 1]]) {
      const j = stack.pop()!;
      answer[j] = i - j;
    }
    stack.push(i);
  }

  return answer;
}
```

### Go

```go
func dailyTemperatures(temps []int) []int {
	answer := make([]int, len(temps))
	stack := []int{} // waiting indices

	for i := range temps {
		for len(stack) > 0 &&
			temps[i] > temps[stack[len(stack)-1]] {
			j := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			answer[j] = i - j
		}
		stack = append(stack, i)
	}

	return answer
}
```

The stack holds indices, not temperatures: when today `i` is warmer than waiting day `j`, the answer for `j` is `i - j`. The comparison is strict (`>`), so an equal day is not a warmer one.

## Complexity

- Time: O(n). Each index is pushed once and popped at most once.
- Space: O(n) extra. The stack grows while temperatures never go up; with all-equal days it holds every index.
- Brute force: O(n²) time in the worst case, about 5 billion comparisons at 100,000 days. On the 8-day example the two are nearly tied, 11 comparisons to 10; the gap only shows at scale.

## Edge cases

- All equal: `[70,70,70,70]` gives `[0,0,0,0]`, because equal is not warmer.
- Equal, then warmer: `[70,70,71]` gives `[2,1,0]`.
- A single day has no later day, so its answer is `[0]`.
- Temperatures that never rise give all zeros, and they fill the stack: its worst case for space.

## Where you'd actually use this

Mostly in interviews. Daily Temperatures is asked at companies like Amazon and Google (source: Educative) because the obvious scan works but is O(n²), and getting to O(n) takes a new idea: keep a stack of the days still waiting for a warmer one.

---

From The Missing README. Want to run your own code and watch every step? Join Cohort 0, the early-access group: https://www.tmread.me/#cohort