Given an array of integers temperatures represents 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.
Example 1:
Input: temperatures = [73,74,75,71,69,72,76,73] Output: [1,1,4,2,1,1,0,0]
Example 2:
Input: temperatures = [30,40,50,60] Output: [1,1,1,0]
Example 3:
Input: temperatures = [30,60,90] Output: [1,1,0]
Constraints:
1 <= temperatures.length <= 10530 <= temperatures[i] <= 100The key idea in Daily Temperatures is to determine how many days you must wait until a warmer temperature appears. A naive approach would compare each day with all future days, leading to O(n^2) time complexity. However, this can be optimized using a Monotonic Stack.
Maintain a stack that stores indices of days with temperatures in a decreasing order. As you iterate through the array, compare the current temperature with the temperature at the index on the top of the stack. If the current temperature is higher, it means you've found the next warmer day for the index at the top. Pop the index and compute the difference in days.
This process ensures each element is pushed and popped at most once. As a result, the algorithm runs efficiently in O(n) time with O(n) auxiliary space for the stack.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Monotonic Stack | O(n) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
If the temperature is say, 70 today, then in the future a warmer temperature must be either 71, 72, 73, ..., 99, or 100. We could remember when all of them occur next.
The monotonic stack approach is an efficient way to solve this problem by maintaining a stack to keep track of temperatures and their indices. We iterate over the temperatures, and for each temperature, we check if it is warmer than the temperature represented by the top index of the stack. If it is, we calculate the difference in indices to determine the number of days to wait for a warmer temperature.
This approach uses a stack to store indices of temperatures that are waiting for a warmer day. As we iterate through the list, for each temperature, we pop from the stack until the current temperature is not warmer than the temperature at the index stored at the top of the stack.
Time Complexity: O(n) - Each index is pushed and popped from the stack once.
Space Complexity: O(n) - Space used by the stack to store indices.
1def dailyTemperatures(temperatures):
2 answer = [0] * len(temperatures)
3 stack = [] # stores indices
4 for i, temp in enumerate(temperatures):
5 while stack and temperatures[stack[-1]] < temp:
6 prev_index = stack.pop()
7 answer[prev_index] = i - prev_index
8 stack.append(i)
9 return answerThe Python solution initializes a list 'answer' filled with zeros. A stack is maintained to store indices of temperatures waiting for a higher temperature. As we iterate through the 'temperatures' list, we compare the current temperature with temperatures indicated by indices in the stack. If the current temperature is higher, that means we have found a higher temperature for the indices in the stack. We then update the 'answer' list with the number of days. Otherwise, the current index is added to the stack.
This approach traverses the temperature list backwards, efficiently discovering the number of days until encountering a warmer temperature. The main idea is to use an array to store the index of the next day for each temperature that is higher. By starting from the end and moving backwards, the solution is optimized in terms of lookups and updates.
Time Complexity: O(n * W) - Where W is the range of temperature values (bounded by a constant, thus linear in practice).
Space Complexity: O(W) - Space used by the array to store the closest warmer day's index.
1function dailyTemperatures(temperatures) {
2Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Daily Temperatures is a common interview-style problem because it tests understanding of stacks, arrays, and the monotonic stack pattern. Variations of the next greater element concept frequently appear in FAANG and other top tech company interviews.
The optimal approach uses a monotonic decreasing stack that stores indices of temperatures. As you traverse the array, you resolve earlier days when a warmer temperature appears. This ensures each element is processed at most twice, giving O(n) time complexity.
A monotonic stack maintains elements in a specific order, allowing you to efficiently find the next greater element. In this problem, it helps determine the next warmer day without repeatedly scanning the array.
A stack is the most suitable data structure, specifically a monotonic stack. It helps efficiently track unresolved temperature indices and quickly determine when a warmer temperature occurs.
The JavaScript implementation leverages a 'next' array to record when the next warmer temperature occurs. The function iterates in reverse order to effectively determine the number of days to wait for a temperature increase.