Daily Temperatures - Leetcode Solution

The Daily Temperatures problem on LeetCode is a problem that asks you to find the number of days you will have to wait until a warmer temperature appears given a list of daily temperatures.

Problem Statement

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature.

If there is no future day for which this is possible, put 0 instead.

Example

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

Solution

The idea of the solution is to use a stack to track the indices of the temperatures. We will iterate through the temperature list from right to left and for each temperature we will pop the stack until we find a temperature that is greater than the current temperature. We will then add the difference in the indices between these two temperatures to the output list. If we do not find a temperature that is greater than the current temperature, we will add 0 to the output list.

Here is the implementation of the solution:

def dailyTemperatures(T):
    stack = []
    result = [0]*len(T)

    for i in range(len(T)-1,-1,-1):
        while stack and T[stack[-1]] <= T[i]:
            stack.pop()

        if stack:
            result[i] = stack[-1] - i

        stack.append(i)

    return result

In the above implementation, we first create an empty stack and a result list of zeros. We then iterate through the temperature list from right to left using the range function with step -1.

For each temperature, we check if the stack is not empty and the last temperature on the stack is less than or equal to the current temperature. If it is, we pop the temperature from the stack until the stack is empty or the last temperature on the stack is greater than the current temperature.

If we have a temperature on the stack after the pop operation, we set the result at the current index to be the difference between the index of the temperature on the stack and the current index. This is the number of days we need to wait until a warmer temperature appears.

Finally, we add the current temperature index to the stack and continue with the next temperature.

We return the result list after the iteration is complete.

Time Complexity

The time complexity of this solution is O(n) where n is the length of the temperature list.

Space Complexity

The space complexity of this solution is O(n) as we are using a stack and result list of size n.

1