Daily Temperatures

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Example 1:

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

Example 2:

Input: temperatures = [30,40,50,60] Output: [1,1,1,0]

Example 3:

Input: temperatures = [30,60,90] Output: [1,1,0]

Constraints:

• 1 <= temperatures.length <= 105
• 30 <= temperatures[i] <= 100

Approach: Monotonic Decreasing Stack (Optimal Solution)

Algorithm

1. Use a stack that stores indices of temperatures waiting for a warmer day
2. Iterate through the array
3. While the stack is not empty and the current temperature is warmer than the temperature at the top index, pop the index and record the distance
4. Push the current index onto the stack
5. Indices left in the stack at the end have no warmer future day, so they remain 0

Key Insight

The stack is maintained in decreasing order of temperature (from bottom to top). When a warmer temperature arrives, it resolves all waiting indices that are colder, filling in their answers in one pass.

Time & Space Complexity

• Time Complexity: O(n) - each index is pushed and popped at most once
• Space Complexity: O(n) - the stack stores indices in the worst case

Java Implementation

import java.util.Stack;

public class DailyTemperatures {

    /**
     * Compute the number of days to wait for a warmer temperature.
     * @param temperatures Array of daily temperatures
     * @return Array where answer[i] is the days until a warmer day (0 if none)
     */
    public static int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] answer = new int[n];
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < n; i++) {
            // Resolve all colder days that this warmer day covers
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int index = stack.pop();
                answer[index] = i - index;
            }
            // Wait for a future warmer day
            stack.push(i);
        }

        return answer;
    }

    // Helper method to print an array
    public static void printArray(int[] arr) {
        System.out.print("[");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
            if (i < arr.length - 1) {
                System.out.print(", ");
            }
        }
        System.out.println("]");
    }

    // Test method
    public static void main(String[] args) {
        // Test case 1
        int[] temp1 = {73, 74, 75, 71, 69, 72, 76, 73};
        System.out.print("Input: ");
        printArray(temp1);
        System.out.print("Output: ");
        printArray(dailyTemperatures(temp1)); // Expected: [1, 1, 4, 2, 1, 1, 0, 0]

        // Test case 2
        int[] temp2 = {30, 40, 50, 60};
        System.out.print("Input: ");
        printArray(temp2);
        System.out.print("Output: ");
        printArray(dailyTemperatures(temp2)); // Expected: [1, 1, 1, 0]

        // Test case 3
        int[] temp3 = {30, 60, 90};
        System.out.print("Input: ");
        printArray(temp3);
        System.out.print("Output: ");
        printArray(dailyTemperatures(temp3)); // Expected: [1, 1, 0]
    }
}

Example Walkthrough

For temperatures = [73,74,75,71,69,72,76,73]:

1. i=0, 73: stack=[0]
2. i=1, 74: 74 > 73, pop 0, answer[0]=1. stack=[1]
3. i=2, 75: 75 > 74, pop 1, answer[1]=1. stack=[2]
4. i=3, 71: not warmer. stack=[2,3]
5. i=4, 69: not warmer. stack=[2,3,4]
6. i=5, 72: 72 > 69, pop 4, answer[4]=1; 72 > 71, pop 3, answer[3]=2. stack=[2,5]
7. i=6, 76: 76 > 72, pop 5, answer[5]=1; 76 > 75, pop 2, answer[2]=4. stack=[6]
8. i=7, 73: not warmer. stack=[6,7]
9. Remaining indices 6 and 7 have no warmer day: answer[6]=0, answer[7]=0

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

Alternative Brute Force Approach (Less Efficient)

public static int[] dailyTemperaturesBruteForce(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;
}

This approach checks every future day for each day, running in O(n²) time.

Key Insights

1. Monotonic Stack: Maintains indices in decreasing temperature order, resolving colder days in one pass
2. Index Storage: The stack stores indices rather than temperatures so distances can be computed
3. Linear Time: Each index enters and leaves the stack exactly once, giving O(n)
4. Remaining Zeros: Indices still on the stack at the end naturally have answer 0

The monotonic stack approach is the optimal solution, providing linear time complexity.