739. Daily Temperatures (Medium)

Problem

Given an integer array temperatures representing daily temperatures, return an array answer such that answer[i] is the number of days after day i until a warmer temperature. If there is no such day, answer[i] == 0.

Example

• temperatures = [73,74,75,71,69,72,76,73] → [1,1,4,2,1,1,0,0]
• temperatures = [30,40,50,60] → [1,1,1,0]
• temperatures = [30,60,90] → [1,1,0]

LeetCode 739 · Link · Medium

Approach 1: Brute force, for each day, scan forward

For each day, linearly search for the first warmer day.

def daily_temperatures(temperatures: list[int]) -> list[int]:
    n = len(temperatures)                          # L1: O(1)
    answer = [0] * n                               # L2: O(n)
    for i in range(n):                             # L3: outer loop, n iterations
        for j in range(i + 1, n):                  # L4: inner scan, up to n-i steps
            if temperatures[j] > temperatures[i]:  # L5: O(1) compare
                answer[i] = j - i                  # L6: O(1) distance
                break
    return answer

Where the time goes, line by line

Variables: n = len(temperatures).

Line	Per-call cost	Times executed	Contribution
L2 (init output)	O(n)	1	O(n)
L3 (outer loop)	O(1)	n	O(n)
L4, L5 (inner scan + compare)	O(1)	up to n per outer	O(n²) ← dominates

Each inner scan can run n-i steps, giving O(n²) in the worst case (monotonically decreasing temperatures).

Complexity

• Time: O(n²), driven by L4/L5 (nested scan).
• Space: O(1) extra.

Approach 2: Scan from right-to-left with a monotonic stack of indices

Walk the array backwards, maintaining a stack of “candidate future warmer days.” For each index, pop stack entries whose temperatures aren’t strictly greater, then the top (if any) is the next warmer day.

def daily_temperatures(temperatures: list[int]) -> list[int]:
    n = len(temperatures)                          # L1: O(1)
    answer = [0] * n                               # L2: O(n)
    stack = []   # stack of indices, strictly decreasing temps toward top
    for i in range(n - 1, -1, -1):                # L3: backward loop, n iterations
        while stack and temperatures[stack[-1]] <= temperatures[i]:  # L4: pop non-warmer
            stack.pop()                            # L5: O(1) amortized
        if stack:
            answer[i] = stack[-1] - i              # L6: O(1) distance to top
        stack.append(i)                            # L7: O(1) push
    return answer

Where the time goes, line by line

Variables: n = len(temperatures).

Line	Per-call cost	Times executed	Contribution
L2 (init output)	O(n)	1	O(n)
L3 (backward loop)	O(1)	n	O(n)
L4-L7 (stack ops)	O(1) amortized	n total pushes/pops	O(n) ← dominates

Each index is pushed once and popped at most once; total stack work across all iterations is O(n).

Complexity

• Time: O(n), driven by L4-L7 (each index pushed and popped at most once).
• Space: O(n) stack.

Approach 3: Forward pass with a monotonic decreasing stack (canonical)

Maintain a stack of indices with strictly decreasing temperatures. For each new day, pop all days on the stack whose temperature is less than today’s, those are answered; today is their warmer day.

def daily_temperatures(temperatures: list[int]) -> list[int]:
    n = len(temperatures)                          # L1: O(1)
    answer = [0] * n                               # L2: O(n) output initialized to 0
    stack = []   # indices of days not yet answered # L3: O(1)
    for i, t in enumerate(temperatures):           # L4: forward loop, n iterations
        while stack and temperatures[stack[-1]] < t:  # L5: pop days answered by today
            j = stack.pop()                        # L6: O(1) amortized pop
            answer[j] = i - j                      # L7: O(1) store distance
        stack.append(i)                            # L8: O(1) push today
    return answer

Where the time goes, line by line

Variables: n = len(temperatures).

Line	Per-call cost	Times executed	Contribution
L2 (init output)	O(n)	1	O(n)
L4 (loop)	O(1)	n	O(n)
L5-L8 (stack ops + answer fill)	O(1) amortized	n total pushes/pops	O(n) ← dominates

Each index is pushed once and popped at most once. The inner while loop is amortized O(1) per outer iteration, giving O(n) total.

Complexity

• Time: O(n), driven by L5-L8 (amortized O(n) total stack work).
• Space: O(n) for the stack and output.

Summary

Approach	Time	Space
Brute force	O(n²)	O(1)
Right-to-left monotonic stack	O(n)	O(n)
Forward monotonic stack	O(n)	O(n)

The forward monotonic-stack form is the canonical template for “next greater element” problems. Memorize it, it appears everywhere (Next Greater Element I/II, Sum of Subarray Minimums, 496).

Test cases

# Quick smoke tests, paste into a REPL or save as test_daily_temperatures.py and run.
# Uses the canonical implementation (Approach 3: forward monotonic stack).

def daily_temperatures(temperatures: list[int]) -> list[int]:
    n = len(temperatures)
    answer = [0] * n
    stack = []
    for i, t in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < t:
            j = stack.pop()
            answer[j] = i - j
        stack.append(i)
    return answer

def _run_tests():
    assert daily_temperatures([73,74,75,71,69,72,76,73]) == [1,1,4,2,1,1,0,0]
    assert daily_temperatures([30,40,50,60]) == [1,1,1,0]
    assert daily_temperatures([30,60,90]) == [1,1,0]
    assert daily_temperatures([90,60,30]) == [0,0,0]
    assert daily_temperatures([70]) == [0]
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

Related data structures

• Arrays, input
• Stacks, monotonic-stack pattern for next-greater