Daily Temperatures medium

Problem Statement

Given an array of integers temperatures representing the daily temperatures, return an array result such that result[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 result[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. Initialization: Create a result array of the same size as the input temperatures array, filled with zeros. This represents the default case where no warmer day is found. Create a stack to store indices of days.

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

3. Stack Operation: For each temperature temperatures[i]:

   • While the stack is not empty and the current temperature temperatures[i] is warmer than the temperature on the top of the stack (temperatures[stack.peek()]), it means we found a warmer day.
   • Pop the index from the stack.
   • Calculate the number of waiting days (i - stack.peek()) and store it in the result array at the popped index.

4. Push to Stack: Push the current index i onto the stack. This index represents a day that we haven't yet found a warmer day for.

5. Return: After iterating through the entire array, return the result array.

Explanation

The algorithm uses a stack to efficiently track days for which we haven't yet found a warmer day. Iterating from right to left ensures that when we encounter a warmer day, we can immediately update the waiting days for all previous days whose temperatures are lower. The stack stores indices, not temperatures, allowing us to directly calculate the number of days using the indices. This right-to-left approach avoids unnecessary comparisons compared to a left-to-right approach.

Code

import java.util.Stack;

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] result = new int[n];
        Stack<Integer> stack = new Stack<>();

        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && temperatures[i] >= temperatures[stack.peek()]) {
                stack.pop();
            }
            result[i] = stack.isEmpty() ? 0 : stack.peek() - i;
            stack.push(i);
        }

        return result;
    }
}

Complexity

• Time Complexity: O(N), where N is the length of the temperatures array. Each element is pushed and popped at most once from the stack.
• Space Complexity: O(N) in the worst case, if the stack needs to store all indices (e.g., a strictly decreasing temperature sequence). In the best case, the space complexity is O(1).