Use a monotonic decreasing stack to find how many days you must wait until a warmer temperature appears.

View Leetcode 739: Daily Temperatures

Monotonic Decreasing Stack Animation

Daily Temperatures uses this idea: when a warmer value arrives, pop all colder values waiting on the stack.

array
100
95
80
76
72
63
83
result
?
?
?
?
?
?
?
Start with an empty monotonic decreasing stack.
stack
Step 1 of 30 · speed 2000ms

Pattern

Use a stack to store indexes whose answer has not been found yet. For Daily Temperatures, the stack is monotonic decreasing by temperature. That means the values on the stack go from warmer to colder as you move from bottom to top.

When the current temperature is warmer than the temperature at the top index of the stack, the current day is the answer for that previous day. Pop that previous day and store the distance between the two indexes.

How to Identify This Pattern

Look for a question asking for the next greater, next warmer, next smaller, or next higher value. These problems often require comparing each item with future items while avoiding a nested loop.

The stack stores values that are waiting for a future value to resolve them. Once the future value arrives, multiple earlier values may be resolved at once.

Daily Temperatures Logic

function dailyTemperatures(temperatures: number[]): number[] {
    const result = new Array(temperatures.length).fill(0);
    const stack: number[] = []; // stores indexes

    for (let i = 0; i < temperatures.length; i++) {
        while (
            stack.length > 0 &&
            temperatures[i] > temperatures[stack[stack.length - 1]]
        ) {
            const previousIndex = stack.pop()!;
            result[previousIndex] = i - previousIndex;
        }

        stack.push(i);
    }

    return result;
}

Complexity

Time complexity is O(n) because each index is pushed once and popped at most once. Space complexity is O(n) for the stack and result array.