Course4all
Join us on telegram
Home/dsa/Stack/Daily Temperatures

Daily Temperatures

Master this topic with zero to advance depth.

Daily Temperatures

Given an array of integers temperatures, return an array answer such that answer[i] is the number of days you have to wait after the i-th day to get a warmer temperature. If there is no future day, keep answer[i] == 0.

Visual Representation

temps = [73, 74, 75, 71, 69, 72, 76, 73] Stack (indices of waiting days): 1. i=0 (73): Push 0. Stack: [0] 2. i=1 (74): 74 > 73. Pop 0, ans[0]=1-0=1. Push 1. Stack: [1] 3. i=2 (75): 75 > 74. Pop 1, ans[1]=2-1=1. Push 2. Stack: [2] 4. i=3 (71): Push 3. Stack: [2, 3] 5. i=4 (69): Push 4. Stack: [2, 3, 4] 6. i=5 (72): 72 > 69. Pop 4, ans[4]=1. 72 > 71. Pop 3, ans[3]=2. Stack: [2, 5] 7. i=6 (76): 76 > 72. Pop 5, ans[5]=1. 76 > 75. Pop 2, ans[2]=4. Stack: [6]
Medium

Examples

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
Approach 1

Level I: Brute Force (Nested Loops)

Intuition

For each day, simply look ahead to the right to find the first day with a higher temperature. This is the most natural approach but is slow for large inputs.

⏱ O(N^2) — for each of the N temperatures, we may scan up to N days forward.💾 O(1) excluding the output array.
java
import java.util.Arrays;

public class Solution {
    public int[] dailyTemperatures(int[] temps) {
        int n = temps.length;
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (temps[j] > temps[i]) {
                    res[i] = j - i;
                    break;
                }
            }
        }
        return res;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(Arrays.toString(sol.dailyTemperatures(new int[]{73,74,75,71,69,72,76,73})));
    }
}
Approach 2

Level III: Optimal (Monotonic Stack)

Intuition

Use a stack to store indices of temperatures that haven't found a warmer day yet. As we iterate, if the current temperature is warmer than the temperature at the index on top of the stack, we've found our 'warmer day' for that index. This efficiently ensures each element is pushed/popped once.

⏱ O(N)💾 O(N)

Detailed Dry Run

iTempActionStack Statusans[idx]
371Push[2, 3]-
469Push[2, 3, 4]-
572Pop 4, Pop 3[2, 5]ans[4]=1, ans[3]=2
676Pop 5, Pop 2[6]ans[5]=1, ans[2]=4
java
import java.util.Stack;
import java.util.Arrays;

public class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] result = new int[n];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int idx = stack.pop();
                result[idx] = i - idx;
            }
            stack.push(i);
        }
        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] res = sol.dailyTemperatures(new int[]{73,74,75,71,69,72,76,73});
        System.out.println(Arrays.toString(res)); // [1,1,4,2,1,1,0,0]
    }
}

⚠️ Common Pitfalls & Tips

Remember that the stack should store indices, not values, so you can calculate the distance between days.

← Previous QuestionEvaluate Reverse Polish Notation
Next Question →Next Greater Element I