4.8.5 — Daily Temperatures

LeetCode 739 · Medium

The problem

For each day, how many days until a warmer temperature? Put 0 if there is never one.

temperatures = [73,74,75,71,69,72,76,73]
answer       = [ 1, 1, 4, 2, 1, 1, 0, 0]

Day 0 is 73 and day 1 is 74, so the wait is 1. Day 2 is 75, and the next warmer day is day 6 at 76, so the wait is 4. Day 6 never gets beaten, so it is 0.

Up to 100,000 days.

The pattern

This is next greater element, and it is the single most useful thing in the stack group.

The brute force scans forward from each day until it finds a warmer one — O(n^2), and it fails at 100,000 days. Name the waste: the same stretch of cool days is rescanned once per earlier day.

Here is the observation that fixes it.

While walking forwards, keep the days that are still waiting for a warmer day. When today's temperature arrives, it resolves every waiting day that is cooler than it — all at once.

And those waiting days are always in decreasing temperature order. Why? Because if a warmer day arrived while a cooler day was still waiting, the cooler one would have been resolved immediately and removed. So a cooler day can never sit behind a warmer one in the waiting list.

That structure — a stack whose values always decrease from bottom to top — is a monotonic stack.

The key idea, stated once

A monotonic stack does not compute anything when an item is pushed. It computes when an item is popped.

The pop is the moment you learn something: this waiting day has just found its warmer day, and it is today. Everything the stack does is triggered by eviction.

Your Report 2 named this exactly right, and it is the sentence that unlocks every problem in this family. If you find yourself trying to work out an answer at push time, you have the model backwards.

The solution

Python

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        answer = [0] * len(temperatures)
        stack = []                        # indices of days still waiting

        for i, temp in enumerate(temperatures):
            while stack and temperatures[stack[-1]] < temp:
                j = stack.pop()           # day j has found its warmer day
                answer[j] = i - j
            stack.append(i)

        return answer                     # days left on the stack keep their 0

TypeScript

function dailyTemperatures(temperatures: number[]): number[] {
  const answer = new Array(temperatures.length).fill(0);
  const stack: number[] = [];

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

  return answer;
}

Store indices, not temperatures. The answer is a distance, so you need positions to subtract. This is the same reason 4.6.6 stores indices.

Days still on the stack at the end never found a warmer day, and the array was initialised to 0, so they are already correct. No cleanup loop is needed.

< and not <=. The problem says warmer, strictly. With equal temperatures the earlier day keeps waiting, which is right.

Trace

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

i	temp	pops (day → answer)	stack after (as temps)
0	73	—	73
1	74	day 0 → 1	74
2	75	day 1 → 1	75
3	71	—	75, 71
4	69	—	75, 71, 69
5	72	day 4 → 1, day 3 → 2	75, 72
6	76	day 5 → 1, day 2 → 4	76
7	73	—	76, 73

Days 6 and 7 stay on the stack and keep their 0.

Notice step 6: one arriving temperature resolved two waiting days. That is the batching that makes the algorithm linear.

Complexity

O(n) time. There is a while inside a for and it is not quadratic.

Every index is pushed exactly once and popped at most once. Across the whole run that is at most n pushes and n pops — 2n operations in total, not n per iteration.

This is the same amortized argument as 4.4.9 and 4.6.6. You will be asked for it every time.

O(n) space, worst case a strictly decreasing input where nothing ever gets resolved.

The four variants

Every "next greater or smaller" problem is this code with two things changed: the comparison, and the direction of travel.

you want	comparison in the while	direction
next greater to the right	stack top < current	left to right
next smaller to the right	stack top > current	left to right
next greater to the left	stack top < current	right to left
next smaller to the left	stack top > current	right to left

Learn the table by deriving it once, not by memorising it. Ask: which items am I keeping, and what makes one useless?

Where this goes next

• Next Greater Element I and II — the same code. Version II has a circular array, handled by walking the array twice and taking indices modulo n.
• Stock Span — next greater to the left, so walk right to left or keep the stack the other way round.
• Largest Rectangle in Histogram — next smaller on both sides, which is 4.8.7 and the hardest problem in this group.
• Trapping Rain Water — the horizontal-layer solution mentioned in 4.5.5 is this structure.
• Remove K Digits, Remove Duplicate Letters — build the smallest possible result by evicting larger digits when a smaller one arrives. Same machinery, different goal.

What the interviewer will push on

"Why is this O(n)?" Each index is pushed once and popped once.

"Why store indices?" The answer is a distance, and only indices give you that.

"What is left on the stack at the end, and why is that correct?" Days that never found a warmer one. The array was initialised to 0.

"Change it to find the next cooler day." Flip the comparison to >. If you can do this without hesitating, you understood the structure.

"Could you do it right to left instead?" Yes — then the stack holds candidates for the future rather than unresolved days from the past, and you read the answer off the top instead of writing it on pop. Both are O(n); the left-to-right version is easier to explain because the pop event carries the meaning.

One thing to volunteer: say the eviction rule as a sentence before writing code. "A cooler earlier day is resolved the moment a warmer day arrives, so the stack only ever holds days still waiting, in decreasing order."

Next: 4.8.6 Car Fleet — a physics puzzle that turns out to be the same eviction idea in disguise.