Daily Temperatures medium

Problem Statement

Given a list of daily temperatures temperatures, return a list of as many as possible daily temperatures T where T[i] is the number of days you have to wait until a warmer temperature occurs. If there is no future day for which this is possible, keep T[i] as 0.

For example:

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

Input: temperatures = [30,40,50,60] Output: [1,1,1,0]

Input: temperatures = [30,60,90] Output: [1,1,0]

Example 1

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

Explanation:

  • temperatures[0] = 73: The next warmer temperature is 74, which is 1 day later.
  • temperatures[1] = 74: The next warmer temperature is 75, which is 1 day later.
  • temperatures[2] = 75: The next warmer temperature is 76, which is 4 days later.
  • temperatures[3] = 71: The next warmer temperature is 72, which is 2 days later.
  • temperatures[4] = 69: The next warmer temperature is 72, which is 1 day later.
  • temperatures[5] = 72: The next warmer temperature is 76, which is 1 day later.
  • temperatures[6] = 76: There is no warmer temperature after this day.
  • temperatures[7] = 73: There is no warmer temperature after this day.

Example 2

Input: temperatures = [30,40,50,60] Output: [1,1,1,0]

Explanation: Each day has a warmer temperature on the next day.

Steps

  1. Initialize Result Array: Create an integer array result of the same size as temperatures, initialized with zeros. This will store the waiting days for each temperature.

  2. Iterate Through Temperatures: Iterate through the temperatures array from right to left (using a for loop starting from the second to last element and decrementing).

  3. Stack for Tracking Warmer Temperatures: Use a stack to store indices of temperatures that could potentially be followed by a warmer temperature. The stack will store indices in increasing order of temperature (from coldest to warmest).

  4. Check for Warmer Temperature: For each temperature at index i, check the top of the stack. If the temperature at the top of the stack is less than the current temperature (temperatures[i]), it means we found a warmer temperature. The number of days to wait is the difference between the current index and the index on the top of the stack (i - stack.Peek()). Update result[stack.Peek()] with this value and pop the index from the stack. Repeat this step until the stack is empty or the top of the stack has a temperature greater than or equal to the current temperature.

  5. Push Current Index: After checking for warmer temperatures, push the current index i onto the stack.

Explanation

The solution uses a stack to efficiently find the next warmer temperature for each day. Iterating from right to left ensures that we always consider future temperatures when searching for a warmer day. The stack keeps track of potential "candidates" – indices of days that might still need to find a warmer day. When a warmer temperature is found, the waiting days are calculated and the candidate is removed from the stack.

Code

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

        for (int i = n - 1; i >= 0; i--) {
            while (stack.Count > 0 && temperatures[stack.Peek()] <= temperatures[i]) {
                stack.Pop();
            }
            result[i] = stack.Count == 0 ? 0 : stack.Peek() - i;
            stack.Push(i);
        }

        return result;
    }
}

Complexity

  • Time Complexity: O(n), where n is the number of temperatures. Each index is pushed and popped at most once onto the stack.
  • Space Complexity: O(n) in the worst case, when the stack holds all indices. In the best case, it could be O(1).