Daily Temperatures - Solution & Explanation
Problem Statement
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] <= 100
Approach Overview
Problem Overview: You receive an array where temperatures[i] represents the temperature on day i. For every day, compute how many days you must wait until a warmer temperature appears. If no warmer day exists, return 0 for that position.
Approach 1: Monotonic Stack (O(n) time, O(n) space)
The optimal solution uses a monotonic decreasing stack that stores indices of days whose warmer temperature hasn't been found yet. As you iterate through the array, compare the current temperature with the temperature at the index on top of the stack. If the current temperature is higher, you've found the next warmer day for that index. Pop the index and compute the distance currentIndex - previousIndex. Continue until the stack is empty or the top temperature is greater than or equal to the current one. Push the current index afterward.
This works because each index is pushed and popped at most once, keeping the algorithm linear. The stack maintains a decreasing sequence of temperatures, which guarantees that when a warmer day appears it resolves multiple previous days efficiently. This is a classic use of stack combined with the monotonic stack pattern commonly used in "next greater element" style problems.
Approach 2: Optimized Array Traversal (O(n) time, O(n) space)
Another strategy scans the array from right to left while using previously computed answers to skip unnecessary checks. Maintain a result array initialized with zeros. For each index i, jump forward using i + result[i] until you find a warmer temperature or reach the end. If temperatures[j] is warmer, store j - i. If not, keep jumping using previously stored answers.
This method avoids an explicit stack but still leverages the idea that future results are already computed. In practice, it behaves similarly to dynamic programming over an array. Each index is visited a limited number of times, keeping overall complexity linear. The approach is useful in languages where array operations are simple and predictable.
Recommended for interviews: The monotonic stack solution is the expected answer. Interviewers often use this problem to test whether you recognize the "next greater element" pattern and can apply a monotonic structure efficiently. Brute force reasoning (checking future days) demonstrates baseline understanding, but implementing the O(n) stack solution shows strong algorithmic pattern recognition.
Approach 1: Monotonic Stack Approach
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.
The 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.
Complexity
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.
Approach 2: Optimized Array Traversal
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.
In this Java solution, we use an auxiliary array 'next' to store the closest index for each possible temperature. By iterating through the temperatures from the end to the beginning, we update the 'next' array and compute the number of days to a warmer temperature for each day.
Code
Java
JavaScript
Complexity
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.
Approach 3: Monotonic Stack
This problem requires us to find the position of the first element greater than each element to its right, which is a typical application scenario for a monotonic stack.
We traverse the array temperatures from right to left, maintaining a stack stk that is monotonically increasing from top to bottom in terms of temperature. The stack stores the indices of the array elements. For each element temperatures[i], we continuously compare it with the top element of the stack. If the temperature corresponding to the top element of the stack is less than or equal to temperatures[i], we pop the top element of the stack in a loop until the stack is empty or the temperature corresponding to the top element of the stack is greater than temperatures[i]. At this point, the top element of the stack is the first element greater than temperatures[i] to its right, and the distance is stk.top() - i. We update the answer array accordingly. Then we push temperatures[i] onto the stack and continue traversing.
After the traversal, we return the answer array.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array temperatures.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Monotonic Stack Approach | Time Complexity: O(n) - Each index is pushed and popped from the stack once. |
| Optimized Array Traversal | Time Complexity: O(n * W) - Where W is the range of temperature values (bounded by a constant, thus linear in practice). |
| Monotonic Stack | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Monotonic Stack | O(n) | O(n) | Best general solution. Ideal for next greater element style problems. |
| Optimized Array Traversal | O(n) | O(n) | When scanning from right to left and reusing computed results is easier than maintaining a stack. |
Video Solution
Daily Temperatures - Monotonic Stack - Leetcode 739 - Python • NeetCode • 372,168 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Daily Temperatures easy or hard?
Daily Temperatures Python/Java solution
How to solve Daily Temperatures in O(n)?
What is the best approach for Daily Temperatures?
Is Daily Temperatures asked at Google/Amazon/Meta?
What data structure is used in Daily Temperatures?
What is the time complexity of Daily Temperatures?
Ready to solve this problem?
Practice Daily Temperatures with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor