Daily Temperatures

Problem in plain words

You get a list of daily temperatures. For each day, report how many days you must wait until a strictly warmer day arrives. If no warmer day ever comes, report 0 for that day.

For example, [50, 40, 60] gives [2, 1, 0]: both 50 and 40 are beaten by 60, and nothing follows 60.

Intuition

Keep a stack of days that are still waiting for a warmer day. Those days are always in decreasing temperature order from bottom to top, because if a warmer day had come later, it would already have resolved the colder ones before it. When a new day arrives, it answers every waiting day on top of the stack that is colder than it, and then it joins the stack to wait itself. The last-in-first-out order is exactly why a stack fits: the most recent waiting day is always the first one a new day can beat.

Approach

1. Create answer filled with 0 and an empty stack of indices.
2. For each index i, while the stack is not empty and temps[i] > temps[top], pop top and set answer[top] = i - top.
3. Push i onto the stack.
4. Indices left on the stack at the end never saw a warmer day; their answers stay 0.

Dry run

Input: [70, 68, 72, 69, 71, 75].

Result: [2, 1, 3, 1, 1, 0].

Java solution

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] answer = new int[n];
        int[] stack = new int[n];   // indices, used as a stack
        int top = -1;
        for (int i = 0; i < n; i++) {
            while (top >= 0 && temperatures[i] > temperatures[stack[top]]) {
                int day = stack[top--];
                answer[day] = i - day;
            }
            stack[++top] = i;
        }
        return answer;
    }
}

Python solution

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        answer = [0] * len(temperatures)
        stack = []   # indices of days still waiting
        for i, temp in enumerate(temperatures):
            while stack and temp > temperatures[stack[-1]]:
                day = stack.pop()
                answer[day] = i - day
            stack.append(i)
        return answer

Complexity

Edge cases and common mistakes

• Equal temperatures: the problem asks for strictly warmer, so pop only on >. Using >= resolves a day with an equally warm one.
• Storing temperatures instead of indices: you need the index to compute the distance; the temperature can always be looked up.
• Brute force: checking every later day for every day is O(n^2) and times out on 10^5 elements.
• All decreasing: nothing is ever popped and the answer is all zeros.