739. Daily Temperatures - Detailed Explanation

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: The direct approach checks, for each day, how far in the future a warmer temperature occurs. For each index i, scan to the right until you reach a temperature greater than temperatures[i]. The logic is correct, but the nested loop costs about O(n²) operations, which is too slow for the largest inputs.

  • Recognize the pattern, next greater element: The question asks for the next greater element (the next warmer temperature) for each day. That framing points to a technique built for exactly this shape: keep a stack of the indices of days that have not yet found a warmer temperature. Each new day then settles every waiting day it beats.

  • Use the constraints (alternate hint): Notice that the temperature range is limited, 30 to 100. If today reads 70, any future warmer temperature must be 71, 72, and so on up to 100. You can record the next occurrence of each possible temperature and read the nearest warmer day out of that table. This alternate approach trades extra space for speed and leans on the small value range.

Approach explanation

This question is an instance of the Monotonic Stack pattern. A monotonic stack is a stack whose stored values only ever rise, or only ever fall, from bottom to top. You enforce that order by popping anything that would break it. Each pop is the moment an earlier element receives its answer. The pattern shows up in enough interviews to sit on most short lists of recurring coding interview patterns, and Daily Temperatures is the cleanest way in.

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 it is too slow for large inputs. The stack solution reaches linear time because every day is settled by the first later day that beats it.

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:

  1. 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).
  2. 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.
  3. 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 finds the correct next warmer day. It is still inefficient for large arrays, because in the worst case it compares every pair of days, which is O(n²) time complexity.

Complexity (brute force): For each of n days, we might scan nearly n days ahead in the worst case. That averages roughly n*(n/2) comparisons, so the time complexity is O(n²). For n = 100,000, the count reaches the order of 10¹⁰ checks, which no judge will accept. Space complexity is O(1) extra, not counting the output array. Treat the brute force as a baseline you improve on, not as a submission.

Approach 2: optimized monotonic stack

Idea: Use a monotonic stack to find the next warmer day for each index in one pass. The stack stores indices of days, and we maintain it so that the temperatures at those indices are in decreasing order. When a new day arrives with a higher temperature, it can settle several waiting days at once.

How it works: We iterate through the list of temperatures and keep a stack of indices.

  • The stack holds indices of days that are waiting for a warmer day. Temperatures on the stack stay in descending order from bottom to top. So the top of the stack is the most recent day that has not found a warmer temperature, and it is cooler than every day 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, day i is the next warmer day for the day at that top index. We pop the top index prev_index and set result[prev_index] = i - prev_index. That records day i as the first later day with a higher temperature for day prev_index.
    • We repeat that step as long as temp is warmer than the temperature at the new top of the stack. Every pop settles one more waiting day.

  • After settling the previous indices, we push the current day i onto the stack, because this day 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 (no warmer day found yet for day i).

  • By the end of the iteration, the indices left in the stack are the days with no future warmer day. Their result values remain 0, the value we initialized.

Each index is pushed once and popped at most once, so the whole scan runs in O(n) time.

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 and 71, with index 3 at temp 71 on top).

  • 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 keep result[6] = 0 and result[7] = 0, the values we initialized. The final result is [1, 1, 4, 2, 1, 1, 0, 0], which matches the expected output.

Each index was pushed once and popped at most once, and the stack skipped comparisons that brute force would have repeated. Day 6 (temp 76) settled day 2 and day 5 in a single step, while brute force would have rechecked days 3, 4, and 5 on behalf of day 2. Grokking the Coding Interview walks this same trace in its Daily Temperatures lesson, which is where the problem is taught alongside the rest of the next-greater-element family.

Why a stack of indices, not temperatures? We store indices rather than temperature values because we need the distance in days. Indices let us compute result[prev_index] = current_index - prev_index the moment a warmer day appears. A temperature value alone would not say how far apart the two days are.

Alternate approach (using a next array): Another efficient solution uses the fact that temperature values range only from 30 to 100. Iterate from the rightmost day to the leftmost, keeping an array of the next occurrence index of each temperature. For each day, check every warmer value (current_temp+1 up to 100) and take the nearest future index among them. This yields an O(n * M) algorithm, where M=71 (the number of possible temperatures from 30 to 100), which is effectively O(n) because M is constant. We will not detail it fully here, but it is a sound use of the constraints and produces the same answers by a different route.

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
Python3
. . . .

Java implementation

Java
Java
. . . .

Explanation: Both implementations keep an answer array initialized with zeros, plus a stack of the indices of days still waiting for a warmer day. We scan the temperature list once. For each day, we pop every cooler earlier day from the stack and write the index difference into its answer, then push the current index. The logic is identical in Python and Java. The test cases cover the example scenarios, and the outputs match the results discussed earlier.

Complexity analysis

  • Brute force approach: Time complexity is O(n²) in the worst case. When temperatures keep decreasing, each day i scans almost every later day before concluding that no warmer day exists. An input like [100, 99, 98, ..., 1] forces the inner loop to run to the end for every i. That quadratic time fails for large n, and n reaches 100k here. 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). The nested while loop looks expensive, but each index is pushed onto the stack once and popped at most once, so the total operations stay proportional to 2n in the worst case. That holds even for n = 100,000. Space complexity is O(n) in the worst case for the stack, which happens when temperatures are strictly decreasing and all n indices pile up. The output array of size n is also used, though any solution needs it. The extra space beyond the output is the stack and a few variables, so 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 each day checks at most 70 possible temperature values, a constant bound. It uses additional space of about 101 slots for the next-occurrence array, plus the result array. That is effectively O(n) time and O(1) extra space, since 101 is constant, and it is a reasonable cost given the problem constraints.

Common mistakes and edge cases

Common mistakes:

  • Not breaking out of the inner loop (brute force): If you forget to break after the first warmer day, the loop keeps scanning. A farther warmer day then overwrites the nearest one. Stop at the first warmer temperature, because the question asks for the number of days until a warmer day, meaning the next one.

  • Using an incorrect comparison: 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. Writing <= pops days with an equal temperature, which is wrong: equal is not warmer, and those days may still find a warmer day later.

  • Forgetting to initialize results to 0: Initialize the result array with zeros. Any day that never finds a warmer future day must output 0. In C++ or Java, confirm the array really starts at zero for the type you chose. In Python, [0]*n handles it.

  • Stack misuse: Pushing temperatures instead of indices complicates the day difference. Push indices, or pairs of index and temperature, so the gap in days is a subtraction. Push temperatures alone and you lose the distance between the days.

  • Off-by-one errors: When computing the difference in days, use j - i, where j is the future warmer day index and i is the current day. That yields the correct number of days in between. Writing (j - i - 1) is incorrect: when j is the very next day we want 1, not 0.

  • Edge case handling: Skipping the edge cases below leads to index errors and wrong answers.

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: Take [80, 75, 72, 70]. No day ever sees a warmer future day, so the output should be all zeros, [0, 0, 0, 0]. The stack approach handles this on its own: it never finds a higher temperature, so it never pops, and every result stays 0.

  • Strictly increasing temperatures: Take [50, 60, 70, 80]. Every day except the last has the next day as warmer, so the output should be [1, 1, 1, 0]. The case is easy, but worth running to confirm that the last day remains 0.

  • All temperatures equal: Take [70, 70, 70, 70]. No future day is strictly warmer, so every entry in the result should be 0. Confirm that your condition does not treat equal as warmer. The stack approach simply accumulates all indices and never pops them, because it never finds a greater temperature.

  • Maximum temperature edge: Days at the highest allowed temperature, 100 here, cannot have a warmer future day, since no permitted value exceeds 100. So any day reading 100 ends with 0 in the result. Both algorithms handle this without a special case: they never find a warmer day for 100, and its result stays 0.

  • Large input performance: An array of length 100,000 still runs quickly with the stack approach. Brute force on the same input will almost certainly time out. Read the constraints first and pick an approach that survives the worst case.

Daily Temperatures is the standard introduction to the Next Greater Element pattern, and the same monotonic stack answers a whole group of questions. Several of them sit on the Blind 75 list, and Grokking the Coding Interview groups them into one chapter so you practice the technique instead of memorizing eight solutions.

Here are some related problems and variations:

  • Next Greater Element II (LeetCode 503): Same question as the basic next greater element, except the array is circular, so the search wraps around to the beginning. A stack still solves it, either by iterating twice through the array or by using modulo indices. It is a small twist on the next greater concept and a monotonic stack again.

  • Next Greater Node in Linked List (LeetCode 1019): You are given a singly linked list and need the next greater value for each node. The concept matches Daily Temperatures, because you still search right for a greater element. Since this is a linked list, you usually copy it into an array, or push nodes onto a stack while traversing, then apply the same strategy. It drills the same pattern in a different data structure.

  • Online Stock Span (LeetCode 901): This question runs the same logic in the opposite direction. For each day's stock price, you report how many consecutive days up to that day the price has been less than or equal to it. It keeps a monotonic decreasing stack of prices, or indices, and computes spans from it. Daily Temperatures searches to the right for a greater element, while Online Stock Span searches to the left, so the stack discipline carries over almost unchanged.

  • Next Smaller Element (variations such as LeetCode 1475, Final Prices With a Special Discount): Some questions ask for the next smaller element instead. In the discount pricing problem, each price takes the next smaller or equal price to its right as a discount. The solution is a monotonic stack again, this time kept in increasing order, so you pop when a smaller element arrives. The technique is not restricted to greater-than comparisons; changing the condition covers next smaller and similar relations.

  • Classic Next Greater Element I (LeetCode 496): This variant gives you two arrays and asks for the next greater element of each value from the first array, searched inside the second. The solution runs a stack over the second array to precompute the next greater value for every element, then answers each query by lookup. It applies the same stack technique to next greater elements, only framed differently.

TAGS
Coding Interview Questions
Coding Interview
CONTRIBUTOR
Arslan Ahmad
Arslan Ahmad
ex-FAANG engineering manager and author or Grokking series.

GET YOUR FREE

Coding Questions Catalog

Design Gurus Newsletter - Latest from our Blog
Boost your coding skills with our essential coding questions catalog.
Take a step towards a better tech career now!
Explore Answers
What is a flex job?
Why Work at Apple? The Reasons People Join and Stay
People join Apple for the reach of the products, the pay and the level of finish, and some leave because of the secrecy.
What language is best for Netflix?
Which cloud is most in demand?
Why do you want to work with Dell Technologies?
What is recursion and when should I use it?
Related Courses
New
Grokking the AI System Design Interview course cover
Grokking the AI System Design Interview
Learn to design AI systems the way interviewers expect: classic ML products, LLM and RAG architectures, and agentic systems, all through the lens of the system design interview.
4.6
(3,192 learners)
Discounted price for Your Region

$99

Grokking the Coding Interview: Patterns for Coding Questions course cover
Grokking the Coding Interview: Patterns for Coding Questions
The 24 essential patterns behind every coding interview question. Available in Java, Python, JavaScript, C++, C#, and Go. The most comprehensive coding interview course with 543 lessons. A smarter alternative to grinding LeetCode.
4.6
Discounted price for Your Region

$197

Grokking Modern AI Fundamentals course cover
Grokking Modern AI Fundamentals
Master the fundamentals of AI today to lead the tech revolution of tomorrow.
4.1
Discounted price for Your Region

$72

Design Gurus logo
One-Stop Portal For Tech Interviews.
About Us
Our Team
Careers
Partners
Contact Us
Become Affiliate
Become Contributor
Social
Facebook
Linkedin
Twitter
Youtube
Substack
LEGAL
Privacy Policy
Cookie Policy
Terms of Service
RESOURCES
Grokking Series
System Design Interview
System Design Framework
System Design Concepts
System Design Questions
Newsletter
INTERVIEW PREP COURSES
Grokking the Coding Interview: Patterns for Coding Questions
Grokking the System Design Interview
Grokking System Design Fundamentals
Advanced System Design Interview, Volume II
Copyright © 2026 Design Gurus, LLC. All rights reserved.