Generated by Codex with GPT-5

Difficulty: MEDIUM

Problem: Daily Temperatures

Problem gist

Given a list of daily temperatures, return a new list where each position says how many days must pass before a strictly warmer temperature appears. If no warmer future day exists, that position should be 0.

For example, if the temperatures are:

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

The answer is:

[1, 1, 4, 2, 1, 1, 0, 0]

Day 2 has temperature 75; the next warmer day is day 6 with temperature 76, so the wait is 4. Day 6 has no warmer future day, so its answer is 0.

Optimal idea

The direct brute-force approach checks every later day for every current day. That is easy to understand, but it can take O(n^2) time when the list is long and mostly decreasing.

The optimal solution keeps a stack of days that have not found their next warmer temperature yet. As the algorithm scans from left to right, the current day can resolve earlier colder days:

1. Look at the unresolved day on top of the stack.
2. If today’s temperature is warmer, today is that day’s first warmer future day.
3. Pop that day and record the distance.
4. Keep popping while today is warmer than the new stack top.
5. Push today as unresolved.

The stack is monotonic: after each day is pushed, temperatures in the stack are non-increasing from bottom to top. That structure matters because if today’s temperature is not warmer than the top day, it cannot be warmer than any earlier day hidden below a hotter or equal top day either.

Each day is pushed once and popped at most once, so the total runtime is O(n).

How to derive it

Start with the question each index asks: “Where is the first warmer day to my right?”

A brute-force scan answers that by looking rightward from each day. The waste is that many days are checked repeatedly. A better way is to reverse the viewpoint. Instead of asking each past day to search the future, let each new day resolve every past day that it can.

When a new temperature arrives, only colder unresolved days can be answered by it. If the most recent unresolved day is colder, the new day is the first warmer day for that index because all days between them were already processed and failed to resolve it. After popping that index, the same logic applies to the next unresolved index.

If the stack top is warmer or equal, stop. The current day cannot answer that top index, and because the stack keeps hotter or equal blockers below it, the current day cannot skip past the top to resolve an older index. Then the current day joins the unresolved stack and waits for a warmer future day.

Python solution

from typing import List


class DailyTemperatureSolver:
    """Compute the wait until a strictly warmer future temperature."""

    def days_until_warmer(self, temperatures: List[int]) -> List[int]:
        waits = [0] * len(temperatures)
        unresolved_indices: List[int] = []

        for current_day, current_temperature in enumerate(temperatures):
            # The current day resolves every colder unresolved day on top.
            while (
                unresolved_indices
                and current_temperature > temperatures[unresolved_indices[-1]]
            ):
                previous_day = unresolved_indices.pop()
                waits[previous_day] = current_day - previous_day

            unresolved_indices.append(current_day)

        return waits


class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        return DailyTemperatureSolver().days_until_warmer(temperatures)

Why this works

The stack contains exactly the days that still need a warmer future day. When processing current_day, any popped previous_day has a lower temperature than the current day. Since the scan moves left to right, every day between previous_day and current_day has already had a chance to resolve previous_day. None did, because previous_day is still on the stack. Therefore current_day is the first warmer future day for previous_day.

The algorithm stops popping when the stack is empty or when the top unresolved day is warmer or equal. At that point, the current day cannot resolve the top day. It also cannot resolve any older day below it, because the stack’s temperatures are kept in non-increasing order from bottom to top. The unresolved top day blocks access to older days that need at least as much warmth.

Every index is appended to the stack once. Once an index is popped, it never returns. That gives O(n) time and O(n) extra space for the answer plus the unresolved stack.

Interview follow-ups

What if the interviewer asks for the next warmer temperature instead of the wait?

The same monotonic stack still works. When the current day pops a colder unresolved day, store current_temperature instead of current_day - previous_day. The reason is identical: the first future day that is warm enough to pop the index is also the next warmer temperature value.

The complexity stays O(n) time and O(n) space. The only real change is the answer format. If the interviewer wants a sentinel for “no warmer temperature,” choose something explicit such as 0, -1, or None depending on the problem statement.

What if a day needs a temperature at least k degrees warmer?

The simple stack condition does not generalize cleanly when k > 1. A day with temperature 75 might be answerable by a future 82, while a more recent unresolved day with temperature 78 is not. If the 78 day sits on top of the stack, it can incorrectly block the older 75 day.

For the original LeetCode temperature range, a practical solution is to scan from right to left and keep the nearest future index for each exact temperature. For day i, check all temperatures from temperatures[i] + k up to the maximum possible temperature and choose the smallest stored index. Then update the stored index for temperatures[i].

With a small fixed temperature range, this is effectively O(n). With a large value range, use a segment tree or balanced structure that can query the minimum future index among all temperatures at least temperatures[i] + k, giving O(n log R) time where R is the number of distinct or compressed temperature values.

What if temperatures arrive as a stream?

The left-to-right monotonic stack is naturally online. Keep the unresolved stack between arrivals. When a new temperature arrives for day d, pop every colder unresolved day and emit or store its wait. Then push day d.

The algorithm cannot finalize days still on the stack until the stream ends, because a warmer day may still arrive later. The amortized cost per incoming temperature is still O(1) because each day is pushed once and popped once, although one particular arrival may pop many older days.

What if the temperatures are circular?

If days wrap around, each index can look through at most the next n - 1 days. A common solution is to simulate two passes over the array using indices modulo n. Process from right to left over 2n positions, keeping a decreasing stack of candidate future indices. For the first pass positions, write answers only for original indices.

The stack must discard candidates that are more than n - 1 days away so an index cannot use itself after a full loop. The complexity remains O(n) because the simulated array has length 2n, and each simulated position is pushed and popped a bounded number of times.

What if the interviewer asks why not scan from right to left?

A right-to-left monotonic stack is also valid. It stores candidate warmer future days rather than unresolved past days. For each current day, pop future days that are colder or equal because they can never be the next warmer day for this day or for any earlier colder day. The next stack top, if one exists, is the nearest warmer future day.

Both directions are O(n). The left-to-right version is often easier to explain because the current day directly resolves previous days. The right-to-left version can be more natural when the interviewer frames the problem as “find the next greater element to the right.”