Stack
Daily Temperatures
medium
Count: 10
DESCRIPTION (inspired by Leetcode.com)
Given an integer array temps representing daily temperatures, write a function to calculate the number of days one has to wait for a warmer temperature after each given day. The function should return an array answer where answer[i] represents the wait time for a warmer day after the ith day. If no warmer day is expected in the future, set answer[i] to 0.
Inputs:
temps = [65, 70, 68, 60, 55, 75, 80, 74]
Output:
[1,4,3,2,1,1,0,0]
Explanation
This question uses a monotonically decreasing stack to find the next greatest temperature for each day in O(n) time, compared to the O(n2) time of the brute-force approach.
A monotonically decreasing stack stores indices, where the temperature values at those indices decrease from bottom to top of the stack. When pushing an index onto this stack, the temperature at that index must be smaller than the temperatures at all other indices currently on the stack.
First, we initialize our stack and our results array. Our stack holds indices of the temperatures in the input array that are waiting for a higher temperature, and our results array holds the number of days we have to wait after the ith day to get a warmer temperature.
Visualization
def dailyTemperatures(temps):n = len(temps)result = [0] * nstack = []for i in range(n):while stack and temps[i] > temps[stack[-1]]:idx = stack.pop()result[idx] = i - idxstack.append(i)return result
daily temperatures
0 / 1
Next, we iterate over each index in the array. For each index, we get the current temperature of that index, and compare it to the temperature of the top index in the stack.
Pushing to the Stack
If the current temperature is less than the top temperature in the stack (or if the stack is empty), we push the current index onto the stack to indicate that we are waiting to find a greater temperature for that index.
Visualization
def dailyTemperatures(temps):n = len(temps)result = [0] * nstack = []for i in range(n):while stack and temps[i] > temps[stack[-1]]:idx = stack.pop()result[idx] = i - idxstack.append(i)return result
initialize variables
0 / 2
Popping from the Stack
When the current temperature is greater than the top temperature in the stack, we have found the next highest temperature for not only the top index in the stack, but potentially other indices in the stack as well, which we can efficiently process due to the monotonically decreasing stack.
We first pop the top index from the stack and calculate the number of days we had to wait for that popped index to find a warmer temperature (current index minus the popped index), and store that number in the results array at the index of the popped element. To account for the fact that the current temperature might be the next greatest temperature for multiple indicies, we repeat this process in a while loop until the current temperature is less than the top temperature in the stack, or until the stack is empty.
After that is done, we push the current index onto the stack to indicate that we have not yet found the next greatest temperature for the current index.
Visualization
def dailyTemperatures(temps):n = len(temps)result = [0] * nstack = []for i in range(n):while stack and temps[i] > temps[stack[-1]]:idx = stack.pop()result[idx] = i - idxstack.append(i)return result
i = 1
0 / 2
Visualization
def dailyTemperatures(temps):n = len(temps)result = [0] * nstack = []for i in range(n):while stack and temps[i] > temps[stack[-1]]:idx = stack.pop()result[idx] = i - idxstack.append(i)return result
push to stack
0 / 9
This continues until we have iterated over the entire input array. At the end, we return the results array.
Efficency of the Monotonically Decreasing Stack
This is more efficient than the brute-force approach because it reduces the number of comparisons we have to make. For example, consider the state of the stack when we are at the 3rd index in the input array.
Visualization
def dailyTemperatures(temps):n = len(temps)result = [0] * nstack = []for i in range(n):while stack and temps[i] > temps[stack[-1]]:idx = stack.pop()result[idx] = i - idxstack.append(i)return result
i = 3
0 / 1
Because the stack is monotonically decreasing, we only have to compare the temperature at i (60) to the temperature of the index at the top of the stack (68), to know that it cannot be a higher temperature for the other remaining items on the stack (70), which avoids a comparision between 60 and 70. But in the brute-force approach, 60 and 70 are compared when finding the next greatest temperature after 70.
Solution
Visualization
Try these examples:
def dailyTemperatures(temps):n = len(temps)result = [0] * nstack = []for i in range(n):while stack and temps[i] > temps[stack[-1]]:idx = stack.pop()result[idx] = i - idxstack.append(i)return result
daily temperatures
0 / 30
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(n) where n is the length of the input array. Each item is pushed and popped from the stack at most once.
Space Complexity: O(n) where n is the length of the input array for the output results array.
Mark as read
Your account is free and you can post anonymously if you choose.