Solution For Daily Temperatures

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

python
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:

“`python
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.

Step by Step Implementation For Daily Temperatures

class Solution {
    public int[] dailyTemperatures(int[] T) {
        int[] ans = new int[T.length];
        Stack stack = new Stack();
        for (int i = T.length - 1; i >= 0; --i) {
            while (!stack.isEmpty() && T[i] >= T[stack.peek()]) stack.pop();
            ans[i] = stack.isEmpty() ? 0 : stack.peek() - i;
            stack.push(i);
        }
        return ans;
    }
}

def dailyTemperatures(T):
        ans = [0] * len(T)
        stack = [] #indexes from hottest to coldest
        for i in range(len(T)):
            while stack and T[i] > T[stack[-1]]:
                cur = stack.pop()
                ans[cur] = i - cur
            stack.append(i)
        return ans

var dailyTemperatures = function(T) {
    // create a stack to store indices
    let stack = [];
    // create an output array with the same length as the input array
    let output = new Array(T.length).fill(0);
    
    for (let i = 0; i < T.length; i++) {
        // while the stack is not empty and the current temperature is greater than the temperature at the top of the stack
        while (stack.length > 0 && T[i] > T[stack[stack.length - 1]]) {
            // the index at the top of the stack is the index of the previous warmer day
            let previousWarmerDayIndex = stack.pop();
            // the difference between the current index and the previous warmer day index is the number of days until the next warmer day
            output[previousWarmerDayIndex] = i - previousWarmerDayIndex;
        }
        // push the current index onto the stack
        stack.push(i);
    }
    
    return output;
};

The problem is as follows:

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.

For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

One solution in C++ is as follows:

vector dailyTemperatures(vector& T) {
    vector ans(T.size());
    stack st;
    for (int i = T.size() - 1; i >= 0; --i) {
        while (!st.empty() && T[i] >= T[st.top()]) st.pop();
        ans[i] = st.empty() ? 0 : st.top() - i;
        st.push(i);
    }
    return ans;
}

public class Solution {
    public int[] DailyTemperatures(int[] T) {
        //Create a stack to keep track of indices
        Stack stack = new Stack();
        
        //Create an array to store the final result
        int[] result = new int[T.Length];
        
        //Loop through the array
        for(int i = 0; i < T.Length; i++){
            //While the stack is not empty and the current value is greater than the value at the top of the stack
            while(stack.Count != 0 && T[i] > T[stack.Peek()]){
                //Pop the top value off the stack and store it in a variable
                int idx = stack.Pop();
                
                //The difference between the current index and the index of the value we just popped off the 
                //stack is the number of days it took for the temperature to increase past the previous day
                result[idx] = i - idx;
            }
            
            //Push the current index onto the stack
            stack.Push(i);
        }
        
        //Return the result array
        return result;
    }
}