Daily Temperatures

Medium

Amazon

2 views

Topics:

ArraysStacks

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 ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

For example:

temperatures = [73,74,75,71,69,72,76,73] should return [1,1,4,2,1,1,0,0]
temperatures = [30,40,50,60] should return [1,1,1,0]
temperatures = [30,60,90] should return [1,1,0]

Write a function that efficiently calculates the waiting days for warmer temperatures.

What is the time and space complexity of your solution? How can the space complexity be further optimized?

Daily Temperatures

Medium

Amazon

2 views

Topics:

ArraysStacks

For example:

temperatures = [73,74,75,71,69,72,76,73] should return [1,1,4,2,1,1,0,0]
temperatures = [30,40,50,60] should return [1,1,1,0]
temperatures = [30,60,90] should return [1,1,0]

Write a function that efficiently calculates the waiting days for warmer temperatures.

What is the time and space complexity of your solution? How can the space complexity be further optimized?

Solution

Brute Force Solution

The brute force solution iterates through each day's temperature and then iterates through the following days to find the first warmer temperature. The number of days between the current day and the warmer day is the result for that day. If no warmer day is found, the result is 0.

def dailyTemperatures_brute_force(temperatures):
    n = len(temperatures)
    answer = [0] * n
    
    for i in range(n):
        for j in range(i + 1, n):
            if temperatures[j] > temperatures[i]:
                answer[i] = j - i
                break
    
    return answer

Time Complexity

O(n^2), where n is the number of days, due to the nested loops.

Space Complexity

O(1), excluding the output array, as we only use a constant amount of extra space.

Optimal Solution Using a Stack

The optimal solution uses a stack to keep track of the indices of days for which we haven't found a warmer day yet. As we iterate through the temperatures, we compare the current day's temperature with the temperatures of the days in the stack. If the current day is warmer than the day at the top of the stack, we have found the waiting days for that day, and we pop the index from the stack and update the answer array. We continue popping until the stack is empty or the current day is not warmer than the day at the top of the stack. Finally, we push the current day's index onto the stack.

def dailyTemperatures(temperatures):
    n = len(temperatures)
    answer = [0] * n
    stack = []
    
    for i in range(n):
        while stack and temperatures[i] > temperatures[stack[-1]]:
            index = stack.pop()
            answer[index] = i - index
        stack.append(i)
    
    return answer

Time Complexity

O(n), where n is the number of days. Each index will be pushed onto the stack and popped off the stack at most once.

Space Complexity

O(n) in the worst case, when the temperatures are monotonically decreasing. In this case, all the indices will be pushed onto the stack.

Edge Cases

Empty Input: If the input array is empty, the code should return an empty array.
Monotonically Decreasing Temperatures: If the temperatures are monotonically decreasing, the output array will be filled with zeros.
Monotonically Increasing Temperatures: If the temperatures are monotonically increasing, the output array will be [1, 1, 1, ..., 0]

Solution

Brute Force Solution

def dailyTemperatures_brute_force(temperatures):
    n = len(temperatures)
    answer = [0] * n
    
    for i in range(n):
        for j in range(i + 1, n):
            if temperatures[j] > temperatures[i]:
                answer[i] = j - i
                break
    
    return answer

Time Complexity

O(n^2), where n is the number of days, due to the nested loops.

Space Complexity

O(1), excluding the output array, as we only use a constant amount of extra space.

Optimal Solution Using a Stack

def dailyTemperatures(temperatures):
    n = len(temperatures)
    answer = [0] * n
    stack = []
    
    for i in range(n):
        while stack and temperatures[i] > temperatures[stack[-1]]:
            index = stack.pop()
            answer[index] = i - index
        stack.append(i)
    
    return answer

Time Complexity

O(n), where n is the number of days. Each index will be pushed onto the stack and popped off the stack at most once.

Space Complexity

O(n) in the worst case, when the temperatures are monotonically decreasing. In this case, all the indices will be pushed onto the stack.

Edge Cases

Empty Input: If the input array is empty, the code should return an empty array.
Monotonically Decreasing Temperatures: If the temperatures are monotonically decreasing, the output array will be filled with zeros.
Monotonically Increasing Temperatures: If the temperatures are monotonically increasing, the output array will be [1, 1, 1, ..., 0]