Back to Main
Learn DSA
Depth-First Search
Greedy Algorithms
Get Premium
Daily Temperatures
DESCRIPTION (credit 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:
Output:
💻 Desktop Required
The code editor works best on larger screens. Please open this page on your computer to write and run code.
"Write a function that takes a list of daily temperatures `temps` and returns 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."
Python
Run your code to see results here
Have suggestions or found something wrong?
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 is one where all elements decrease in value (from the bottom of the stack to the top). When pushing an item on a monotonically decreasing stack, it must be smaller than all the other elements that are 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.
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
1x
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 (of 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.
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
1x
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.
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
1x
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
1x
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.
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
1x
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
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
1x
Complexity Analysis
Time Complexity: O(n). 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.
Login to track your progress
Your account is free and you can post anonymously if you choose.