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] = 0 instead.

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 an empty list answer of the same length as temperatures to store the results. Also, create an empty 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 temperature at the top of the stack (temperatures[stack[-1]]) is less than or equal to the current temperature (temperatures[i]):

     • Pop the index from the stack.
     • Calculate the waiting days: waiting_days = i - stack[-1] (if the stack is not empty after popping). If the stack is empty after popping, it means there's no warmer day in the future.
     • Assign the waiting_days to answer[stack[-1]].

   • Push the current index i onto the stack.

4. Return: Return the answer list.

Explanation:

The solution uses a stack to efficiently track the indices of days with temperatures that are waiting for a warmer day. Iterating from right to left allows us to easily find the next warmer day for each day by comparing with the temperatures already processed. The stack stores indices in decreasing order of temperature. When we encounter a warmer day, we can immediately find how many days we need to wait by calculating the difference in indices. If the stack is empty after popping, it means there's no warmer day in the future.

Code:

def dailyTemperatures(temperatures):
    n = len(temperatures)
    answer = [0] * n
    stack = []  # Stack to store indices

    for i in range(n - 1, -1, -1):
        while stack and temperatures[stack[-1]] <= temperatures[i]:
            stack.pop()
        if stack:
            answer[i] = stack[-1] - i
        stack.append(i)

    return answer

Complexity:

• Time Complexity: O(N), where N is the length of the temperatures array. Each element is pushed and popped from the stack at most once.
• Space Complexity: O(N) in the worst case, if the stack grows to the size of the input array (e.g., monotonically decreasing temperatures). In the best case it is O(1).