Daily Temperatures medium

Problem Statement

Given an array of integers temperatures representing 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] as 0.

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]

Steps

1. Initialize the result array: Create an array answer of the same size as temperatures, filled with zeros. This represents the default case where no warmer day is found.

2. Use a stack: Employ a stack to store indices of days. The stack will store indices in descending order of temperature.

3. Iterate through the temperatures: Iterate through the temperatures array from right to left (this is crucial for efficiency).

4. Stack operations: For each temperature:

   • While the stack is not empty and the current temperature is warmer than the temperature at the top of the stack:
     • Pop the index top from the stack.
     • Calculate the number of waiting days: answer[top] = i - top. i is the current index.
   • Push the current index i onto the stack.

5. Return the result: After iterating through all temperatures, return the answer array.

Explanation

The algorithm utilizes a stack to efficiently track indices of days with temperatures. The stack maintains a monotonically decreasing order of temperatures. When a warmer temperature is encountered, it means we've found a warmer day for the days whose indices are at the top of the stack. The difference between the current index and the index at the top of the stack is the number of days we need to wait. Iterating from right to left ensures we always find the closest warmer day.

Code

function dailyTemperatures(temperatures: number[]): number[] {
    const n = temperatures.length;
    const answer: number[] = new Array(n).fill(0);
    const stack: number[] = []; // Stack to store indices

    for (let i = n - 1; i >= 0; i--) {
        while (stack.length > 0 && temperatures[stack[stack.length - 1]] <= temperatures[i]) {
            stack.pop();
        }
        if (stack.length > 0) {
            answer[i] = stack[stack.length - 1] - i;
        }
        stack.push(i);
    }

    return answer;
};

Complexity

• Time Complexity: O(N), where N is the length of the temperatures array. Each index is pushed and popped at most once from the stack.
• Space Complexity: O(N) in the worst-case scenario, where the stack could potentially hold all the indices if the temperatures are monotonically decreasing. In the best case (monotonically increasing temperatures), the space complexity is O(1).