Daily Temperatures – 739. LeetCode

You are given a list of daily temperatures. For each day, you need to figure out how many days you must wait until the temperature becomes warmer. If there’s no future day with a warmer temperature, just put 0 for that day. The result will be a new list showing the number of days to wait for each day.

Brute Force Approach

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;
}

• The outer loop picks a day (i).
• The inner loop checks future days (j) to find the first warmer day.
• If found, the difference in days (j – i) is stored in the result array.

The brute-force solution is simple but inefficient, as it compares every pair of days, making it slow for large inputs.

Optimal Algorithm: Monotonic Decreasing Stack

The monotonic stack exists to efficiently solve problems where you need to find the “next” or “previous” element that satisfies some condition, like being greater or smaller, in a list of numbers. Instead of checking every element in the list multiple times (as in brute force), the monotonic stack allows you to quickly skip over elements that are no longer relevant.

This solution uses a monotonic decreasing stack where the elements in the stack are always arranged from largest to smallest as you go from the bottom to the top.

Why Is It Great for Comparisons Over Ranges of Data?

A monotonic stack shines for problems like finding the next greater or smaller element because:

1. Efficiency: Each element is pushed to and popped from the stack only once, making the algorithm O(n).

2. Focus on Relevant Data: By maintaining order, it keeps only the indices or values you still need to process, skipping unnecessary work.

3. Forward or Backward Traversal: You can easily adapt the stack for forward (next) or backward (previous) comparisons.

Optimized Code

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: Define Variables

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

• result is where the final answer will be stored and returned.

• The stack is used to keep track of indices for temperatures that haven’t yet found a warmer day.

Step 2: Iterate Through the Temperatures

for (int i = 0; i < n; i++) {

• Iterating from left to right (beginning to end) is natural for forward comparisons like finding “next warmer day.”

Step 3: Check for a Warmer Temperature

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

• Continuously checks the top of the stack (more recent unresolved day) to see if the current temperature is warmer than the temperature at the index stored at the top of the stack.
• This is the core comparison step. If a warmer day is found for a previously unresolved day, the index is processed.

Step 4: Pop the Index

int index = stack.pop();

• Removes the index of the day at the top of the stack and stores it in index.
• Once a warmer temperature is found, the unresolved day at the top of the stack no longer needs to remain unresolved.
• Using pop() to remove indices ensures stack integrity and avoids unnecessary memory use.

Step 5: Calculate the Number of Days

result[index] = i - index;

• Computes the difference the current day (i) and the previously unresolved day (index). This value represents how many days the unresolved day had to wait for a warmer temperature.
• Direct computation ensures the result array is built efficiently and without additional iterations.

Step 6: Push Current Index

stack.push(i);

• Adds the current index (i) onto the stack for future comparison.
• Pushing indices ensures the algorithm works with minimal memory overhead and avoids modifying the input array directly.

Step 7: Return

return result;

• Using a dedicated result array avoids modifying the input and adheres to the functional programming paradigm for clarity and maintainability.

Why This Code Works

1. Optimal Time Complexity:

Each element is pushed and popped from the stack only once, resulting in O(n) time complexity.

2. Clear Separation of Concerns:

The code separates:

• Data preparation (result and stack initialization).

• Core logic (loop and comparison).

• Output (return statement).

3. Efficient Memory Use:

The monotonic stack ensures minimal extra space, only storing necessary indices at any point in time.

4. Readable and Maintainable:

Each step of the algorithm is straightforward and adheres to common Java coding practices, making it easier to understand and debug.