Daily Temperatures

PracticeNeetCode ↗LeetCode ↗

Given an array of daily temperatures, return an array where answer[i] is the number of days you'd have to wait after day i for a warmer temperature. If no future day is warmer, put 0.

Example

Key Pointers

• This is a "next greater element" problem — the standard tool for that shape is a monotonic decreasing stack.
• When the current temperature beats the temperature at the stack's top index, that's the answer for that index — pop it and record the day gap.
• Each index is pushed and popped at most once, which is what keeps this O(n) instead of the O(n²) brute-force scan-ahead.

Step-by-Step Analysis

1. Create an empty stack (holding indices) and a result array of zeros, same length as temperatures.
2. For each index i, temperature t: while the stack isn't empty and t is warmer than the temperature at the stack's top index, pop that index and set result[popped] = i - popped.
3. Push the current index i onto the stack.
4. Any indices still on the stack after the loop never found a warmer day, so they stay 0 (the default).

Complexity

Time: O(n) — Space: O(n)

Code

def dailyTemperatures(temperatures: list[int]) -> list[int]:
    result = [0] * len(temperatures)
    stack = []

    for i, t in enumerate(temperatures):
        while stack and t > temperatures[stack[-1]]:
            prev_index = stack.pop()
            result[prev_index] = i - prev_index
        stack.append(i)

    return result

Code Explanation

How the solution above works, piece by piece.

1. result starts as all 0 ("no warmer day"), and the stack holds indices of days still waiting for a warmer day.
2. For each day i, pop every waiting day that is colder than today: today is their first warmer day, so their answer is i - prev_index.
3. Then push today; it now waits too.
4. The stack stays in decreasing temperature order (a monotonic stack), so each day is pushed once and popped at most once: O(n) total.
5. Days never popped (76, 73) keep the default answer 0.

Visual Walkthrough

Running it on temperatures = [73, 74, 75, 71, 69, 72, 76, 73]:

Video Explanation

NeetCode — Daily Temperatures, LeetCode 739