Daily Temperatures

Problem

LeetCode 739 — Daily Temperatures

Given an array temperatures where temperatures[i] is the temperature on day i, return an array result where result[i] is the number of days you have to wait after day i to get a warmer temperature. If there is no future day with a warmer temperature, result[i] = 0.

Example

temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
result       = [ 1,  1,  4,  2,  1,  1,  0,  0]

• Day 0 (73°): next warmer is day 1 (74°) → 1 day.
• Day 2 (75°): next warmer is day 6 (76°) → 4 days.
• Day 6 (76°): no warmer day → 0.

Approach

Walk left-to-right, maintaining a monotonic stack of indices for days whose “next warmer day” is still unresolved.

For each index i:

1. While the stack is non-empty and temperatures[stack.peek()] < temperatures[i]:
   • Pop index j.
   • result[j] = i - j (today is the first warmer day for day j).
2. Push i.

After the loop, every index still on the stack has no warmer future day — result stays 0 there (pre-initialized).

Why this works

The stack is always in decreasing temperature order from bottom to top. When a warmer day arrives it resolves every day colder than it in one sweep. Each index is pushed once and popped at most once → O(n) total work.

Complexity

• Time: O(n)
• Space: O(n) for the stack (worst case: strictly decreasing temperatures, everything stays on the stack)

Solution

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] result = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
                int j = stack.pop();
                result[j] = i - j;
            }
            stack.push(i);
        }

        return result;
    }
}

Why It Teaches You Something

The same monotonic-stack skeleton solves a whole family of problems:

Once you see that the stack enforces a monotone invariant on unresolved work, you start recognizing these problems on sight.