Daily Temperatures

NeetCode: Daily Temperatures · LeetCode: 739. Daily Temperatures · Difficulty: Medium

Given daily temperatures, return an array where answer[i] is the number of days after day i until a warmer temperature, or 0 if there is none.

Example

Text

Input:  temperatures = [30, 38, 30, 36, 35, 40, 28]
Output: [1, 4, 1, 2, 1, 0, 0]

Brute force: scan forward from each day

Java

import java.util.Arrays;

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] answer = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (temperatures[j] > temperatures[i]) {
                    answer[i] = j - i;
                    break;
                }
            }
        }
        return answer;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(Arrays.toString(s.dailyTemperatures(new int[]{30, 38, 30, 36, 35, 40, 28})));
        System.out.println(Arrays.toString(s.dailyTemperatures(new int[]{22, 21, 20})));
    }
}

Output

[1, 4, 1, 2, 1, 0, 0]
[0, 0, 0]

Each answer entry starts at 0, the value for "no warmer day". j - i is an int index difference, so no cast is needed.

Time: O(n²). Space: O(1) beyond the output.

Optimal: monotonic stack of waiting days

Keep a stack of indices (an ArrayDeque<Integer> used through push, pop, and peek) of days still waiting for a warmer day; their temperatures are non-increasing from bottom to top. When today is warmer than the day on top of the stack, that day's wait ends today: pop it and record i - j, where i is today and j is the popped day. Repeat, then push today.

Java

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

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] answer = new int[temperatures.length];
        Deque<Integer> stack = new ArrayDeque<>(); // indices of days still waiting
        for (int i = 0; i < temperatures.length; i++) {
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int j = stack.pop();
                answer[j] = i - j;
            }
            stack.push(i);
        }
        return answer;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(Arrays.toString(s.dailyTemperatures(new int[]{30, 38, 30, 36, 35, 40, 28})));
        System.out.println(Arrays.toString(s.dailyTemperatures(new int[]{22, 21, 20})));
    }
}

Output

[1, 4, 1, 2, 1, 0, 0]
[0, 0, 0]

Time: O(n): each index is pushed and popped once. Space: O(n).