739. Daily Temperatures

Description

The problem requires us to determine how many days one must wait until a warmer temperature occurs for each day in a list of daily temperatures. If there is no future day with a warmer temperature, the output for that day should be 0.

Intuition

A brute-force solution would involve checking for each day how many days it takes until a warmer day is found. However, this would be inefficient due to its high time complexity. A more efficient approach involves using a stack to keep track of indices of days that haven't found a warmer day yet. By iterating through the list of temperatures and comparing the current temperature with those on the stack, we can find the correct waiting days more efficiently.

Approach

1. Initialization: Create a list result initialized to 0 with the same length as temperatures. Also, initialize an empty stack to keep track of pairs of temperatures and their indices.
2. Iterate through temperatures: For each temperature in the list, do the following: - While the stack is not empty and the current temperature is greater than the temperature at the top of the stack, pop the stack. For each popped element, calculate the difference between the current index and the popped index and store it in the result list at the popped index. - Push the current temperature and its index onto the stack.
3. Return the result: The result list will now contain the number of days required to encounter a warmer temperature for each day.

Complexity

Time Complexity:

O(n), where n is the number of days in the list. Each element is pushed and popped from the stack at most once, leading to a linear time complexity.

Space Complexity:

O(n) due to the space required for the result list and the stack.

Code

C++

class Solution {
public:
    vector dailyTemperatures(vector& temperatures) {
        vector result(temperatures.size(), 0);
        stack> stack; // stores pair of (temperature, index)

        for (int i = 0; i < temperatures.size(); ++i) {
            int temp = temperatures[i];
            while (!stack.empty() && temp > stack.top().first) {
                auto [t, index] = stack.top();
                stack.pop();
                result[index] = i - index;
            }
            stack.push({temp, i});
        }

        return result;
    }
};

Python

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        result = [0] * len(temperatures)
        stack = []  # stores pair of (temperature, index)

        for i, temp in enumerate(temperatures):
            while stack and temp > stack[-1][0]:
                pop = stack.pop()
                result[pop[1]] = i - pop[1]
            stack.append((temp, i))
        
        return result

Java

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] result = new int[temperatures.length];
        Stack stack = new Stack<>(); // stores pair of (temperature, index)

        for (int i = 0; i < temperatures.length; i++) {
            int temp = temperatures[i];
            while (!stack.isEmpty() && temp > stack.peek()[0]) {
                int[] pop = stack.pop();
                result[pop[1]] = i - pop[1];
            }
            stack.push(new int[]{temp, i});
        }

        return result;
    }
}

JavaScript

var dailyTemperatures = function(temperatures) {
    result = Array(temperatures.length).fill(0)
    stack = [] 
    for (const [i, temp] of temperatures.entries()) {

        while (stack.length > 0 && temp > stack.at(-1)[0]) {
            pop = stack.pop()
            result[pop[1]] = i-pop[1]
        }
        stack.push([temp, i])
    }
    return result
};