739. Daily Temperatures - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Given an array of integers temperatures representing the daily temperatures, the task is to determine, for each day, how many days you would have to wait until a warmer temperature occurs. If there is no future day with a higher temperature, the answer for that day is 0.

Example 1:
Input: temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1, 1, 4, 2, 1, 1, 0, 0]

Explanation: On day 0 (temp 73), the next warmer day is day 1 (temp 74), so output[0] = 1. On day 1 (74), the next warmer day is day 2 (75) → output[1] = 1. On day 2 (75), the next warmer day is day 6 (76) → output[2] = 4. Day 3 (71) sees a warmer day at day 5 (72) → output[3] = 2. Day 4 (69) warms up on day 5 (72) → output[4] = 1. Day 5 (72) warms on day 6 (76) → output[5] = 1. Day 6 (76) has no future warmer day → output[6] = 0. Day 7 (73) is the last day, no future warmer day → output[7] = 0.

Example 2:
Input: temperatures = [30, 40, 50, 60]
Output: [1, 1, 1, 0]
Explanation: Each day is warmer than the previous one, so for days 0,1,2 the next warmer day is just the next day (output 1). The last day has no warmer future day (0).

Example 3:
Input: temperatures = [30, 60, 90]
Output: [1, 1, 0]
Explanation: Day 0 (30) warms by day 1 (60) → 1 day, day 1 (60) warms by day 2 (90) → 1 day, day 2 (90) has no warmer day after → 0.

Constraints:

1 <= temperatures.length <= 10^5 (up to 100,000 days)
30 <= temperatures[i] <= 100 (each temperature is between 30 and 100, inclusive)

Hints

Brute Force Idea: A straightforward approach is to check, for each day, how far in the future a warmer temperature occurs. This means for each index i, scan to the right until finding a temperature greater than temperatures[i]. This works but will be inefficient for large input (nested loop ~ O(n²) operations).
Recognize the Pattern – Next Greater Element: The problem is essentially asking for the next greater element (next warmer temperature) for each day. This suggests using a strategy to efficiently find the next greater value for each element. One common approach for next greater element problems is to use a stack to keep track of indices of days that haven't found a warmer temperature yet.
Use Constraints (Alternate Hint): Notice the temperature range is limited (30 to 100). If today's temperature is, say, 70, any future warmer temperature must be 71, 72, ..., up to 100. We could leverage this by remembering the next occurrence of each possible temperature. For instance, we might keep an array of the next index where each temperature appears and use that to find the nearest warmer day. (This is an alternate optimized approach using extra space, taking advantage of the small range.)

Approach Explanation

We will discuss two approaches: a Brute Force approach and an Optimized Monotonic Stack approach. The brute force solution is easier to think of but can be too slow for large inputs, whereas the stack solution leverages a stack data structure to achieve linear time complexity by finding next warmer days more efficiently.

Approach 1: Brute Force (Naive)

Idea: For each day, scan forward to find the next day with a higher temperature. Once a warmer day is found, calculate the difference in days. If no such day exists, the result is 0 for that index.

Steps:

Initialize an answer array result of the same length as temperatures with all values set to 0 (default for days that never get a warmer day in the future).
Iterate through each day index i from 0 to n-1:
- For each day i, look at each subsequent day j = i+1, i+2, ...:
  - If temperatures[j] is greater than temperatures[i], set result[i] = j - i (the number of days until the warmer temperature) and break out of the inner loop (stop at the first warmer day).
- If the inner loop finishes without finding a warmer day, result[i] remains 0.
Return the result array.

Example Trace (Brute Force): Suppose temperatures = [73, 72, 76].

For day 0 (temp 73), check day 1 (72, not warmer), then day 2 (76, warmer). We find a warmer day at j=2, so result[0] = 2 (wait 2 days).
For day 1 (temp 72), check day 2 (76, warmer) → result[1] = 1.
Day 2 has no days after it, so result[2] stays 0.
The output would be [2, 1, 0]. This simple approach correctly finds the next warmer day but is inefficient for large arrays because in the worst case it checks every pair of days (O(n²) time complexity).

Complexity (Brute Force): For each of n days, we might scan nearly n days ahead in the worst case, leading to roughly n*(n/2) comparisons on average, i.e., O(n²) time complexity. For n = 100,000, this could be on the order of 10¹⁰ checks, which is not feasible. Space complexity is O(1) extra (not counting the output array). This brute force approach will time out for large inputs and is primarily a thought exercise or a baseline to improve upon.

Approach 2: Optimized Monotonic Stack

Idea: Use a monotonic stack to efficiently find the next warmer day for each index in one pass. The stack will store indices of days, and we maintain it such that the temperatures of those indices are in decreasing order on the stack. This way, when we encounter a new day with a higher temperature, we can resolve (answer) multiple previous days at once.

How It Works: We iterate through the list of temperatures, and use a stack of indices:

The stack holds indices of days that are waiting for a warmer day. We ensure that temperatures on the stack are in descending order (from bottom to top). This means the top of the stack is the index of the most recent day that hasn't found a warmer temperature and is cooler than all days whose indices are below it in the stack.
For each new day i with temperature temp = temperatures[i], we compare temp with the temperature at the index on top of the stack.
- While the stack is not empty and temp is warmer than the temperature at the stack's top index, it means we've found the next warmer day for the day at that top index. We pop the top index prev_index from the stack and set result[prev_index] = i - prev_index. This records that the current day i is the next day with a higher temperature for day prev_index.
- We repeat the above step as long as the current temperature temp is warmer than the temperature at the new top of the stack (each pop finds a day that temp resolves).
After processing warmer days for previous indices, we push the current day i onto the stack (because this day itself now waits for a future warmer day).
If the stack is empty or the current temperature is not higher than the stack's top, we simply push the current index on the stack (meaning no warmer day found yet for day i).
By the end of the iteration, any indices still remaining in the stack are those days for which no future warmer day exists, and their result values remain 0 (which we initialized).

This approach ensures each index is pushed to and popped from the stack at most once, giving linear time complexity O(n).

Step-by-Step Example (Monotonic Stack):
Consider temperatures = [73, 74, 75, 71, 69, 72, 76, 73] (from Example 1). We will walk through the algorithm and track the stack and result:

Initialize: result = [0,0,0,0,0,0,0,0], stack = [] (empty).
Day 0 (temp=73): Stack is empty, push index 0.
Stack now: [0] (represents temperature 73).
Day 1 (temp=74): Compare with temp at stack top (index 0 -> 73). 74 > 73, so day 1 is warmer than day 0.
Pop index 0 from stack, and set result[0] = 1 (day1 - day0 = 1 day wait).
Stack becomes empty. Push index 1.
Stack now: [1] (represents temp 74).
Day 2 (temp=75): Compare with temp at stack top (index 1 -> 74). 75 > 74, so day 2 is warmer than day 1.
Pop index 1, set result[1] = 1 (day2 - day1 = 1).
Stack now empty. Push index 2.
Stack: [2] (represents temp 75).
Day 3 (temp=71): Compare with temp at stack top (index 2 -> 75). 71 is not warmer (71 < 75), so we do not pop.
Just push index 3.
Stack: [2, 3] (temps 75, 71 – stack top is index 3 with temp 71).
Day 4 (temp=69): Compare with temp at stack top (index 3 -> 71). 69 < 71, not warmer, push index 4.
Stack: [2, 3, 4] (temps 75, 71, 69).
Day 5 (temp=72): Compare with stack top (index 4 -> 69). 72 > 69, warmer than day4.
Pop index 4, set result[4] = 5 - 4 = 1. (Day 5 is 1 day after day 4 and is warmer.)
New stack top is index 3 (temp 71). 72 > 71, still warmer.
Pop index 3, set result[3] = 5 - 3 = 2. (Day 5 is 2 days after day 3 and warmer.)
New stack top is index 2 (temp 75). 72 < 75, not warmer, stop popping.
Push index 5.
Stack: [2, 5] (temps 75, 72).
Day 6 (temp=76): Compare with stack top (index 5 -> 72). 76 > 72, warmer than day5.
Pop index 5, set result[5] = 6 - 5 = 1.
New top is index 2 (temp 75). 76 > 75, warmer than day2.
Pop index 2, set result[2] = 6 - 2 = 4.
Stack is now empty (as we popped indices 5 and 2).
Push index 6.
Stack: [6] (temp 76).
Day 7 (temp=73): Compare with stack top (index 6 -> 76). 73 < 76, not warmer.
Push index 7.
Stack: [6, 7] (temps 76, 73).
End of array: The stack [6, 7] means indices 6 and 7 never found a warmer day in the future. They remain with result[6] = 0 and result[7] = 0 (which we had initialized). The final result now is [1, 1, 4, 2, 1, 1, 0, 0], which matches the expected output.

During this process, each index was pushed once and popped at most once, and we efficiently skipped over many comparisons that the brute force method would perform. For example, day 6 (temp 76) directly resolved day 2 and day 5 in one go, whereas brute force would have checked day 3,4,5 in between for day 2. This monotonic stack method is both efficient and a common technique for “next greater element” problems.

Why a stack of indices (not temperatures)? We store indices on the stack (rather than the temperature values) because we need to compute the difference in days. Using indices allows us to calculate result[prev_index] = current_index - prev_index when a warmer day is found. Also, the temperature value alone wouldn’t tell us how far apart the days are.

Alternate Approach (Using Next Array): Another efficient solution uses the fact that temperature values range only from 30 to 100. We can iterate from rightmost day to leftmost, keeping an array of the next occurrence index of each temperature. For each day going backward, we can look for the next warmer temperature by checking all possible warmer values (current_temp+1 up to 100) and take the nearest future index among those. This yields an O(n * M) algorithm, where M=71 (the number of possible temperatures from 30 to 100), effectively O(n) since M is constant. While we won’t detail this approach fully here, it’s a clever use of constraints (space-time tradeoff) and produces the same result with a different technique.

Code Implementation

Below are implementations of the optimized stack approach in Python and Java. Both solutions use the monotonic stack strategy described above to achieve efficient performance. We also include some test cases to verify the correctness of the solutions.

Python Implementation

Python3

. . . .

Java Implementation

Java

. . . .

Explanation: In both implementations, we maintain an array answer initialized with 0s. We use a stack to keep track of indices of days that haven't found a warmer day yet. We iterate through the temperature list once; for each day, we pop all cooler previous days from the stack and fill their answers with the current index difference. Then we push the current index. The logic is identical in Python and Java. The test cases demonstrate the example scenarios: the outputs match the expected results discussed earlier.

Complexity Analysis

Brute Force Approach: Time complexity is O(n²) in the worst case. If the temperatures keep decreasing, each day i will scan through almost all later days to find a warmer temperature (or conclude there is none). For example, an input like [100, 99, 98, ..., 1] forces the inner loop to run to the end for every i. This quadratic time will fail for large n (n up to 100k). Space complexity is O(1) extra (aside from the output list) since we only use a few variables.
Monotonic Stack Approach: Time complexity is O(n). Although we have a nested while loop, each element index is pushed onto the stack once and popped at most once, so the total operations are proportional to 2n in the worst case. This linear complexity is efficient even for n = 100,000. Space complexity is O(n) in the worst case for the stack (in the scenario where temperatures are strictly decreasing, the stack could grow to hold all n indices). The output array of size n is also used, but that’s required for any solution. The additional space beyond output is the stack and a few variables, making it O(n) extra.

Proof of O(n) for stack approach: Every index goes onto the stack once. It can only be popped when a future day with higher temperature is found. Each index is popped at most one time, so the while loop across the entire run will execute at most n pops in total. Thus, the overall operations (pushes+pops) are bounded by 2n, which is linear.

Alternate Constraint-based Approach: If implemented, it also runs in O(n) time because for each day we check at most 70 possible temperature values (constant bound) to find the next warmer day. It uses additional space of size ~101 for the next-occurrence array (plus the result array). This is effectively O(n) time and O(1) extra space (since 101 is constant) – a very reasonable complexity given the problem constraints.

Common Mistakes and Edge Cases

Common Mistakes:

Not Breaking Out of Inner Loop (Brute Force): In the brute force approach, forgetting to break after finding the first warmer day will cause you to continue checking later days. This can overwrite the result with a farther warmer day instead of the nearest one. Always stop at the first warmer temperature because the problem asks for the number of days until a warmer day (the next one, not a later one).
Using Incorrect Comparison: Ensure you look for strictly greater temperatures. A temperature that is equal or lower is not a “warmer” day. In the stack approach, the while condition should be while (... < currentTemp) (strictly less than). Using <= by mistake would pop days that have equal temperature, which is wrong because an equal temperature is not warmer and those days might still find a warmer day later.
Forgetting to Initialize Results to 0: It's important to initialize the result array with 0s. Any day that never finds a warmer future day must output 0. If using languages like C++ or Java without initialization, or if using an array of a different type, make sure to set default 0s. In Python, using [0]*n takes care of this.
Stack Misuse: Pushing temperatures instead of indices on the stack can complicate calculating the day difference. Always push indices (or pairs of index and temp) so that you can compute the difference in days easily. If you push temperatures only, you'll lose the information of how far apart the days are.
Off-by-One Errors: When computing the difference in days, ensure you do j - i (if j is the future warmer day index and i is the current day). This yields the correct number of days in between. Some might confuse this and do (j - i - 1), which would be incorrect because if j is the very next day, we want 1, not 0.
Edge Case Handling: Not considering edge cases (listed below) can lead to mistakes such as index out of range or logical errors.

Edge Cases to Consider:

Single Day: If temperatures has length 1, the output should be [0] because there are no future days at all.
Strictly Decreasing Temperatures: e.g. [80, 75, 72, 70]. Here, no day ever sees a warmer future day, so the output should be all zeros ([0, 0, 0, 0]). The stack approach naturally handles this by never finding a higher temp to cause pops, leaving all results as 0.
Strictly Increasing Temperatures: e.g. [50, 60, 70, 80]. Every day except the last has the next day as warmer. Output should be [1, 1, 1, 0]. This is an easy scenario but good to verify the logic (especially that the last day remains 0).
All Temperatures Equal: e.g. [70, 70, 70, 70]. Since no future day is strictly warmer (all are equal), every entry in the result should be 0. Make sure the algorithm doesn’t mistakenly treat equal as warmer. The stack approach will simply accumulate all indices and never pop them because it never finds a greater temperature.
Max Temperature Edge: If some days have the maximum allowed temperature (100° in this problem), those days cannot have a warmer future day (because no allowed temperature exceeds 100). For example, if the input includes 100, any day at 100 will have 0 in the result unless a later day somehow had a value above 100 (impossible given constraints). Our algorithms inherently handle this (they will never find a warmer day for 100, leaving its result as 0).
Large Input Performance: An array of length 100,000 should still run efficiently with the stack approach. If you were to accidentally use the brute force approach on such an input, it would likely time out. Always consider the constraints and choose an approach that can handle the worst case.

This problem is a classic example of the Next Greater Element pattern. Mastering it can help in many similar problems. Here are some related problems and variations:

Next Greater Element II (LeetCode 503): Similar to the basic next greater problem, but the array is treated in a circular fashion (the search for the next greater wraps around to the beginning of the array). This can also be solved with a stack by iterating twice through the array (or using modulo indices). It’s a twist on the next greater concept and also uses a monotonic stack.
Next Greater Node in Linked List (LeetCode 1019): You are given a singly linked list and need to find the next greater value for each node. The concept is the same as daily temperatures (find next greater element to the right), but since it's a linked list, you typically convert it to an array (or use a stack while traversing) to apply the same stack strategy. It reinforces the same pattern in a different data structure context.
Online Stock Span (LeetCode 901): This is almost the mirror image of Daily Temperatures in terms of logic. For each day’s stock price, the task is to find how many consecutive days up to that day the price has been less or equal (span of days the stock price has not dropped). It uses a monotonic decreasing stack of prices (or indices) to compute spans. While daily temperatures looks to the right for a greater element, stock span looks to the left for a greater element (or counts how many days until a greater element on the left appears). The stack technique (maintaining decreasing order) is very similar.
Next Smaller Element (Variations like LeetCode 1475 "Final Prices with a Special Discount"): Instead of next greater, some problems ask for the next smaller element. For example, in the discount pricing problem, for each price you find the next smaller or equal price to the right and subtract it for a discount. The approach again uses a monotonic stack, but kept in increasing order (so we pop when we find a smaller element). This is a good reminder that the monotonic stack idea isn’t limited to greater-than comparisons; it works for next smaller or other similar comparisons by adjusting the condition.
Classic Next Greater Element I (LeetCode 496): In this variant, you are given two arrays and need to find the next greater element of each element of the first array within the second array. The core of the solution is using a stack on the second array to precompute next greater for every element, which is then looked up for answering the first array’s queries. It’s a direct application of the stack technique for next greater elements, just framed differently.