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

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

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

function dailyTemperatures(temperatures: number[]): number[] {
    const n = temperatures.length;                          // L1: O(1)
    const answer = new Array(n).fill(0);                    // L2: O(n)
    for (let i = 0; i < n; i++) {                          // L3: outer loop, n iterations
        for (let j = i + 1; j < n; j++) {                 // 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;
}

final class Solution {
    func dailyTemperatures(_ temperatures: [Int]) -> [Int] {
        temperatures.indices.map { day in
            for future in (day + 1)..<temperatures.count where temperatures[future] > temperatures[day] { return future - day }
            return 0
        }
    }
}

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

function dailyTemperatures(temperatures: number[]): number[] {
    const n = temperatures.length;
    const answer = new Array(n).fill(0);           // L2: O(n)
    const stack: number[] = [];
    for (let i = n - 1; i >= 0; i--) {            // L3: backward loop, n iterations
        while (stack.length && temperatures[stack[stack.length - 1]] <= temperatures[i])
            stack.pop();                           // L4-L5: O(1) amortized
        if (stack.length) answer[i] = stack[stack.length - 1] - i;  // L6: O(1) distance
        stack.push(i);                             // L7: O(1) push
    }
    return answer;
}

final class Solution {
    func dailyTemperatures(_ temperatures: [Int]) -> [Int] {
        var answer = Array(repeating: 0, count: temperatures.count)
        var stack: [Int] = []
        for day in temperatures.indices.reversed() {
            while let last = stack.last, temperatures[last] <= temperatures[day] { stack.removeLast() }
            if let warmer = stack.last { answer[day] = warmer - day }
            stack.append(day)
        }
        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.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

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

function dailyTemperatures(temperatures: number[]): number[] {
    const n = temperatures.length;
    const answer = new Array(n).fill(0);           // L2: O(n) output initialized to 0
    const stack: number[] = [];                    // L3: O(1)
    for (let i = 0; i < n; i++) {                 // L4: forward loop, n iterations
        while (stack.length && temperatures[stack[stack.length - 1]] < temperatures[i]) {  // L5
            const j = stack.pop()!;               // L6: O(1) amortized pop
            answer[j] = i - j;                    // L7: O(1) store distance
        }
        stack.push(i);                             // L8: O(1) push today
    }
    return answer;
}

final class Solution {
    func dailyTemperatures(_ temperatures: [Int]) -> [Int] {
        var answer = Array(repeating: 0, count: temperatures.count)
        var stack: [Int] = []
        for day in temperatures.indices {
            while let last = stack.last, temperatures[day] > temperatures[last] { answer[stack.removeLast()] = day - last }
            stack.append(day)
        }
        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.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

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).

# 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()

function dailyTemperatures(temperatures: number[]): number[] {
    const n = temperatures.length;
    const answer = new Array(n).fill(0);
    const stack: number[] = [];
    for (let i = 0; i < n; i++) {
        while (stack.length && temperatures[stack[stack.length - 1]] < temperatures[i]) {
            const j = stack.pop()!;
            answer[j] = i - j;
        }
        stack.push(i);
    }
    return answer;
}

console.assert(JSON.stringify(dailyTemperatures([73,74,75,71,69,72,76,73])) === JSON.stringify([1,1,4,2,1,1,0,0]));
console.assert(JSON.stringify(dailyTemperatures([30,40,50,60])) === JSON.stringify([1,1,1,0]));
console.assert(JSON.stringify(dailyTemperatures([30,60,90])) === JSON.stringify([1,1,0]));
console.assert(JSON.stringify(dailyTemperatures([90,60,30])) === JSON.stringify([0,0,0]));
console.assert(JSON.stringify(dailyTemperatures([70])) === JSON.stringify([0]));
console.log('all tests pass');

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

Monotonic Stack, the ordered stack pattern for nearest greater, nearest smaller, and spans.
Array Scans, the linear pass habit of carrying just enough state while reading each item once.

739. Daily Temperatures (Medium)

Problem

Try it yourself

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

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

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

Summary

Test cases

Related data structures

Related concepts