Daily Temperatures

Daily Temperatures is a monotonic stack problem. For each day, we need to know how many days we must wait until a warmer temperature appears.

The trick is to store unresolved day indices on a stack. When a warmer day arrives, it resolves every colder previous day on top of the stack.

Problem

Given an array temperatures, return an array answer where answer[i] is the number of days after day i until a warmer temperature.

If no future day is warmer, answer[i] should be 0.

Example:

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

First Attempt

public int[] dailyTemperatures(int[] temperatures) {
    var n = temperatures.length;
    var result = new int[n];

    Deque<Integer> prevIndices = new ArrayDeque<>();

    for (var i = 0; i < n; i++) {
        while (!prevIndices.isEmpty()
                && temperatures[i] > temperatures[prevIndices.peek()]) {
            var prevIndex = prevIndices.pop();
            result[prevIndex] = i - prevIndex;
        }

        prevIndices.push(i);
    }

    return result;
}

This is the right approach.

The stack stores indices whose warmer future day has not been found yet.

Clean Version

import java.util.ArrayDeque;
import java.util.Deque;

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

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

            stack.push(i);
        }

        return answer;
    }
}

Why Store Indices

We need the distance between days:

i - previousDay

If the stack stored only temperatures, we could know a warmer day exists, but not how many days it took.

So the stack stores unresolved indices.

Monotonic Stack Shape

The stack is monotonic decreasing by temperature.

That means temperatures at stored indices go from warmer to colder as we move toward the top.

When a new temperature is warmer than the top unresolved day, that previous day is resolved.

Keep popping while the current temperature is warmer:

while (!stack.isEmpty()
        && temperatures[i] > temperatures[stack.peek()]) {
    int previousDay = stack.pop();
    answer[previousDay] = i - previousDay;
}

Then push the current day because it is now waiting for its own warmer future day.

Walkthrough

Input:

[73, 74, 75, 71, 69, 72, 76, 73]

Important moments:

day	temp	action
0	73	push day 0
1	74	warmer than day 0, answer[0] = 1
2	75	warmer than day 1, answer[1] = 1
3	71	colder, push day 3
4	69	colder, push day 4
5	72	warmer than day 4 and day 3, answer[4] = 1, answer[3] = 2
6	76	warmer than day 5 and day 2, answer[5] = 1, answer[2] = 4
7	73	no unresolved colder day on top, push day 7

Days left on the stack have no warmer future day, so their answer stays 0.

Complexity

Approach	Time	Space
Brute force look ahead	`O(n^2)`	`O(1)`
Monotonic stack	`O(n)`	`O(n)`

Each index is pushed once and popped at most once, so the total work is linear.

Takeaways

Use a monotonic stack when each item waits for the next greater future item.
Store indices when the answer requires distance or position.
Pop while the current value resolves previous values.
Unresolved indices left on the stack keep the default answer 0.