Daily Temperatures – 739. LeetCode

The problem Daily Temperatures asks you to analyze a list of daily temperatures and determine, for each day, how many days you need to wait to see a warmer temperature. If no warmer day exists in the future, the result for that day is 0. For example, given temperatures like [73, 74, 75, 71, 69, 72, 76, 73], the output should be [1, 1, 4, 2, 1, 1, 0, 0]. This means, for instance, on day 0 (temperature 73), you only need to wait 1 day to see a warmer temperature (74 on day 1). If a day has no warmer temperature in the future, like day 6 (temperature 76), the output is 0. The goal is to calculate these “waiting days” efficiently.

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

• Outer Loop: Iterates through each temperature as the current day.

• Inner Loop: Checks all subsequent days to find the first warmer temperature.

• If a warmer day is found, the difference in days is calculated and stored in the result array.

• This method examines every possible pair of days, making it simple but inefficient.

Optimal Algorithm and Data Structure

Algorithm: Monotonic Decreasing Stack

• A monotonic decreasing stack keeps elements in decreasing order. The largest elements are at the bottom, and the smallest elements are at the top.

Steps of the Algorithm

1. Initialize an empty stack to store indices.

2. Create a result array initialized to 0.

3. Iterate through the temperature array:

• While the stack is not empty and the current temperature is greater than the temperature at the index on the top of the stack:

• Pop the stack, calculate the difference in indices, and update the result for the popped index.

• Push the current index onto the stack.

4. Return the result array.

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

Line By Line Explanation

Step 1: Create Data Structures

int n = temperatures.length;
int[] result = new int[n];
Deque<Integer> stack = new ArrayDeque<>();

• result: An array where each index will store the number of days until warmer weather.
• stack: A stack to store indices of day with unresolved warmer weather.

Step 2: Check Each Day’s Temperature

for (int i = 0; i < n; i++) {
    // Process logic for each day's temperature
}

• This loop ensures every day is processed to determine how many days until warmer weather.

Step 3: Process Warmer Days

while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {

• Checks if the stack is not empty and the current temperature is warmer than the temperature at the index stored at the top of the stack.
• If true, it means we’ve found the next warmer day for the index at the top of the stack.
• This condition ensures that the stack only holds indices of days that still need a warmer day to be calculated.

Step 4: Calculate Days To Wait

int index = stack.pop();
result[index] = i - index;

• Pops the index from the top of the stack, as we’ve now determined its next warmer day.
• Calculates the number of days to wait for warmer temperature as i – index and stores it in the result array.
• It minimizes the number of operations by processing each index only when a warmer temperature is found.

Step 5: Push Current Day Onto The Stack

stack.push(i);

• Pushes the current day’s index (i) onto the stack to be processed later if no warmer day has been found yet.

Step 5: Return the Results

return result;

Why the Code Was Coded This Way:

• The stack structure ensures linear time complexity by eliminating unnecessary comparisons.

• The separation of pushing and popping actions maintains clarity and aligns with the monotonic stack pattern.

• Using a deque provides efficient stack operations, making the solution clean and concise.