Daily Temperatures

This is the classic monotonic-stack problem, and the one to master first: every other "next greater" problem is a small change to it. The naive answer is quadratic and obvious. The stack answer is linear, and its correctness rests on one observation about which days can still be waiting.

It also looks like real work. "For each order, how long until a bigger one?" and "for each stock price, how many days until it is beaten?" are the same question.

The problem

You are given a list of daily temperatures. For each day, return how many days you must wait until a strictly warmer day. If no warmer day comes, return 0 for that day.

• [73, 74, 75, 71, 69, 72, 76, 73] → [1, 1, 4, 2, 1, 1, 0, 0]. Day 2 (75) waits until day 6 (76): 4 days. Days 6 and 7 never see anything warmer.
• [30, 40, 50, 60] → [1, 1, 1, 0]. Every day is beaten by the next one.
• [60, 50, 40] → [0, 0, 0]. Nothing is ever warmer.

Constraints: 1 ≤ n ≤ 10⁵, temperatures between 30 and 100.

Clarifying questions

• Strictly warmer, or warmer-or-equal? Strictly. An equal day does not end the wait.
• Distance or temperature? The number of days, a distance.
• What if no warmer day comes? 0.
• Is one day possible? Yes: [50] → [0].

Approach 1: the simple way

For each day, scan forward until you find a warmer one.

1def daily_temperatures_brute(temps: list[int]) -> list[int]:2    """For each day, scan forward for a warmer one: O(n^2)."""3    answer = [0] * len(temps)4    for i in range(len(temps)):5        for j in range(i + 1, len(temps)):6            if temps[j] > temps[i]:7                answer[i] = j - i8                break9    return answer

Time: O(n²). Space: O(1) beyond the answer.

On a falling series — each day colder than the last — no inner loop ever breaks early. At n = 10⁵, that is about 5 × 10⁹ comparisons, which takes minutes in Python.

Look at the waste. When day 5 scans forward past days 6, 7 and 8, day 4 will scan those same days again, and day 3 after that. The same comparisons are repeated over and over.

The key insight

Scan left to right, and think about the days that are still waiting for a warmer day. Two facts:

1. The waiting days are in decreasing order of temperature. Suppose a waiting day were warmer than an earlier waiting day. Then the earlier day's wait would already be over — this later day is warmer than it. So among the days still waiting, each is no warmer than the one before it.
2. A new day answers the waiting days from the most recent backward. When today's temperature arrives, the waiting days that are colder than today have found their answer: today. Because the waiting days are in decreasing order, the colder ones are all at the recent end. Stop at the first waiting day that is not colder; everything before it is warmer still.

A list that you add to at one end and remove from at the same end, most recent first, is a stack. And because the answer is a distance, today - day, the stack must hold indices, not temperatures.

In the example, when 72 arrives on day 5, the days waiting are day 2 (75), day 3 (71) and day 4 (69). The 72 answers day 4 (1 day) and day 3 (2 days), then stops at day 2, because 75 is warmer than 72.

Approach 2: a monotonic stack of waiting days

1def daily_temperatures(temps: list[int]) -> list[int]:2    """Days to wait for a warmer day, or 0 if none comes."""3    answer = [0] * len(temps)4    stack: list[int] = []                        # indices of days still waiting5    for today, temp in enumerate(temps):6        while stack and temps[stack[-1]] < temp:7            day = stack.pop()8            answer[day] = today - day            # a distance, so we stored indices9        stack.append(today)10    return answer                                # days left on the stack keep 0

Dry run on [73, 74, 75, 71, 69, 72, 76, 73]:

Days 6 and 7 are still waiting at the end and keep their 0. The result is [1, 1, 4, 2, 1, 1, 0, 0]. The last column is always decreasing — that is the "monotonic" in monotonic stack.

Time: O(n). There were 8 pushes and 6 pops in total. Each index is pushed once and popped at most once, so the while loop runs at most n times across the whole run, never n times per day. Space: O(n) for the stack; a falling series keeps every day on it.

Approach 3: right to left, reusing answers

There is a version with no stack. Go from the last day to the first. For day i, start at j = i + 1. If day j is not warmer, you do not need to check the days between j and j's own warmer day — they are all no warmer than j, so no warmer than i either. Jump straight to j + answer[j]. If answer[j] is 0, nothing after j is warmer than j, so nothing is warmer than i.

1def daily_temperatures_jumps(temps: list[int]) -> list[int]:2    """Right to left, reusing answers already found as jumps: O(1) extra space."""3    n = len(temps)4    answer = [0] * n5    for i in range(n - 2, -1, -1):6        j = i + 17        while temps[j] <= temps[i] and answer[j] > 0:8            j += answer[j]                       # skip straight to the next day warmer than j9        if temps[j] > temps[i]:10            answer[i] = j - i11    return answer

On the example, day 2 (75) starts at day 3 (71), jumps to day 5 (72), jumps to day 6 (76), which is warmer: answer 4. Three looks instead of four.

Time: O(n) — the jumps from day i + 1 follow the same chain of days that a right-to-left stack would hold, and a day that is jumped over is never visited again by an earlier day, so the total number of jumps is at most n. Space: O(1) beyond the answer. All three versions were checked against each other on 500 random inputs.

Edge cases

• Falling series: no pops at all; every answer stays 0; the stack grows to n.
• Rising series: every day pops the one before it; the stack never holds more than one index.
• Equal temperatures, like [70, 70, 71]: with <, the second 70 does not pop the first; both wait, and 71 answers both: [2, 1, 0].
• One day: [0].

Follow-ups

• "Return the warmer temperature, not the wait." Store temp in answer[day] instead of today - day.
• "The days wrap around, as in a circle." Walk the list twice; see Next Greater Element II.
• "Stock span: for each day, how many consecutive days up to today had a price at most today's?" The mirror image: pop while the top's price is at most today's, and the span is today minus the new top (or today + 1 if the stack is empty).