Daily Temperatures

Problem Statement

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 $i^{th}$ day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

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

Approach: Monotonic Stack

To efficiently find the next greater element (in this case, the next warmer day), we can use a Monotonic Decreasing Stack. Instead of storing the temperatures themselves, the stack will store the indices of the days. This allows us to easily calculate the distance (number of days) between two temperatures.

1. Initialize an array res of the same length as temperatures, filled with 0. This handles cases where no warmer day is found.
2. Initialize an empty stack to keep track of the indices of the days we haven’t found a warmer temperature for yet.
3. Iterate through each day i and its temperature in the array:
   • While the stack is not empty AND the current temperature is strictly greater than the temperature at the index on the top of the stack:
     • We have found a warmer day for the day at the top of the stack!
     • Pop the index from the stack (let’s call it prevIndex).
     • Calculate the number of days waited: i - prevIndex.
     • Set res[prevIndex] = i - prevIndex.
   • Push the current day’s index i onto the stack so we can find its next warmer day later.
4. After the loop, return the res array.

Solution

/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
function dailyTemperatures(temperatures) {
    const res = new Array(temperatures.length).fill(0);
    const stack = []; // Stores indices
    
    for (let i = 0; i < temperatures.length; i++) {
        const t = temperatures[i];
        
        // While current temp is warmer than the temp at the index on top of the stack
        while (stack.length > 0 && t > temperatures[stack[stack.length - 1]]) {
            const prevIndex = stack.pop();
            res[prevIndex] = i - prevIndex;
        }
        
        stack.push(i);
    }
    
    return res;
}

Complexity Analysis

• Time Complexity: $O(n)$, where $n$ is the length of the temperatures array. Although there is a nested while loop, every index is pushed onto the stack exactly once and popped from the stack at most once. Thus, the inner loop runs at most $n$ times globally.
• Space Complexity: $O(n)$ in the worst case (e.g., temperatures are strictly decreasing like [100, 90, 80, 70]), where the stack will store all $n$ indices.