Problem 739

Abstract / Summary

Given a list of daily temperatures, output for each day how many days until a warmer temperature occurs.

Note

The full problem description, including helpful examples, can be found on LeetCode.

C++ 0739.cpp

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        reverse(temperatures.begin(), temperatures.end());

        vector<int> result;
        result.reserve(temperatures.size());

        const int maxtemp = 100;
        const int invalid = -1;
        vector<int> last(maxtemp + 1, invalid);
        for (int i = 0; i < temperatures.size(); i++)
        {
            auto current = temperatures[i];

            // optimize
            const int scan = 10;
            if (i > scan)
            {
                bool fast = false;
                for (int j = 1; j < scan; j++)
                    if (temperatures[i - j] > current)
                    {
                        fast = true;
                        result.push_back(j);
                        break;
                    }

                if (fast)
                {
                    last[current] = i;
                    continue;
                }
            }

            int best = invalid;
            for (int j = current + 1; j < last.size(); j++)
                if (best < last[j] && last[j] != invalid)
                {
                    best = last[j];
                    if (best == i - 1)
                        break;
                }

            if (best == invalid)
                result.push_back(0);
            else
                result.push_back(i - best);

            last[current] = i;
        }

        reverse(result.begin(), result.end());
        return result;
    }
};
56 lines | 1584 bytes | submitted August 10, 2023 | GitHub   2% comment ratio | tab size 4

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 69% (2+ million submissions).

Typical patterns to solve this problem:
  • Array
  • Monotonic Stack
  • Stack
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The function dailyTemperatures computes, for each day, the number of days one must wait until a warmer temperature occurs. The implementation works by processing the input array in reverse order, maintaining auxiliary structures that allow fast lookup of the next higher temperature, and applying a short-range scan optimization for recent days. The result is built in reverse as well and finally reversed to match the original order.

Core Algorithm

The algorithm proceeds in three conceptual phases: reversal of the input, iterative processing with two complementary lookup strategies, and final reversal of the output.

Input Reversal

reverse(temperatures.begin(), temperatures.end());

Reversing the temperature list enables the algorithm to treat the problem as “find the next greater element to the left” while iterating forward. This direction simplifies index arithmetic because the distance to a warmer day becomes the difference between the current index and the index of the previously seen higher temperature.

Result Buffer Allocation

vector<int> result;
result.reserve(temperatures.size());

The result vector is pre-allocated with the exact capacity needed, avoiding repeated reallocations as elements are appended. This contributes to steady-time insertion performance.

Tracking Last Occurrence of Each Temperature

const int maxtemp = 100;
const int invalid = -1;
vector<int> last(maxtemp + 1, invalid);

A fixed-size array last stores, for each possible temperature value (0-100), the most recent index where that temperature appeared while scanning the reversed list. An invalid sentinel marks temperatures that have not yet been encountered. Because the temperature range is bounded, direct indexing provides O(1) access without hash tables or binary search structures.

Main Loop

for (int i = 0; i < temperatures.size(); i++)
{
    auto current = temperatures[i];
    // ... (optimizations and lookup)
}

The loop iterates over each reversed temperature. Inside the loop two distinct mechanisms determine the distance to the next warmer day.

Short-Range Scan Optimization

const int scan = 10;
if (i > scan)
{
    bool fast = false;
    for (int j = 1; j < scan; j++)
        if (temperatures[i - j] > current)
        {
            fast = true;
            result.push_back(j);
            break;
        }

    if (fast)
    {
        last[current] = i;
        continue;
    }
}

When the current position is beyond a small constant window (scan = 10), the algorithm first checks the most recent ten days for a warmer temperature. If a warmer day is found within this window, the distance j is immediately recorded, the last entry for the current temperature is updated, and the loop proceeds to the next iteration. This fast path avoids the more expensive full-range search for the majority of cases where a warmer day lies nearby.

Full-Range Lookup Using last

int best = invalid;
for (int j = current + 1; j < last.size(); j++)
    if (best < last[j] && last[j] != invalid)
    {
        best = last[j];
        if (best == i - 1)
            break;
    }

if (best == invalid)
    result.push_back(0);
else
    result.push_back(i - best);

last[current] = i;

If the short-range scan does not succeed, the algorithm scans the last array for any temperature higher than the current one. It keeps the most recent index (best) among those higher temperatures. The inner condition best < last[j] ensures that only the closest future warmer day is considered. An early exit occurs when the closest possible candidate (i - 1) is found, because no later index can improve the distance.

When no higher temperature has been seen (best == invalid), the result for that day is 0, indicating that no warmer day exists in the future. Otherwise, the distance i - best is stored. Finally, the last entry for the current temperature is updated to the current index, making it available for subsequent iterations.

Output Reversal

reverse(result.begin(), result.end());
return result;

Because the algorithm built the answer while scanning the reversed input, the result vector is also reversed before being returned, restoring the original chronological order.

Edge Cases Handled

The implementation gracefully handles the situation where the input contains the maximum possible temperature (100). Since the last array is sized to maxtemp + 1, the index 100 is valid, and the loop that searches higher temperatures (j = current + 1; j < last.size(); ++j) naturally terminates without accessing out-of-bounds memory.

When the temperature list is empty, the reversal operations are no-ops, the loop body never executes, and the function returns an empty vector, matching the expected behavior for an empty input.

If a day is the hottest among all remaining days, the best variable remains invalid, leading to a 0 entry in the result. This correctly signals that no future warmer day exists for that position.

The short-range scan guard if (i > scan) prevents out-of-range indexing when the current index is less than the scan window size, ensuring that the inner loop never accesses negative indices.

Performance Optimizations

The code incorporates several deliberate optimizations:

  • Pre-allocation of the result vector eliminates dynamic resizing overhead during the main loop.
  • Fixed-size temperature index array (last) provides constant-time updates and lookups, leveraging the known bounded temperature range.
  • Short-range scan with a small constant (scan = 10) captures the common case where a warmer day lies within the recent past, allowing the algorithm to bypass the more expensive full scan of the last array.
  • Early termination inside the full-range lookup (if (best == i - 1) break;) stops the search as soon as the closest possible warmer day is identified, reducing unnecessary iterations.
  • In-place reversal of both the input and output vectors avoids auxiliary copies, keeping memory usage low and cache locality high.

Collectively, these techniques ensure that the function runs efficiently even for large input sizes, balancing the cost of occasional full scans with frequent fast path completions.

written by openai gpt

ELI5 - Simplified Explanation

Imagine you have a long row of thermometers showing the temperature for many days. This code helps figure out how many days you have to wait until it gets warmer than it is today.

First, the code flips all the thermometers around to look at them starting from the very last day and working backward to the first. It keeps a magic notebook called last that remembers the most recent time a certain temperature happened. As it goes through the days, it checks if it already knows when a warmer day occurred by looking at the numbers saved in that notebook.

If the thermometer is feeling clever, it quickly checks a few days nearby to see if the answer is easy to find. If that does not work, it searches through its notebook to find the closest day that was warmer than today. It writes down how many days are between now and that future warm day. If it cannot find any day that is warmer, it writes down zero instead. Once all the days are checked, the code flips the list of answers back to the right order so everything is correct.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 26 | median = 4.5 | μ = 4.54 | σ = 1.50

Complexity Analysis

not analyzed yet

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Python Java TS
WalkCCC C++ Python Java
leetcode.ca C++ Python Java Rust JS Go TS
LeetcodeHelp C++ Python Java
Progiez C++ Python Java
github BigEggStudy C#
black-shadows C++
bujosa Rust
chandansgowda Python
charles-wangkai Java
everthis JS
fartem Ruby
FelixFan1122 C#
fengvyi C++
fpdjsns C++
fsq Python
halfrost Go
JoshCrozier JS
keineahnung2345 C++
lkwq007 Python
MacJim C++
ruoru Rust
shreymehul C#
suxrobGM C#
trung-hn Python
varunu28 Java
vthwang Java
wisdompeak C++
yuanliu666 Kotlin
zfang399 C++
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, Go, Java, JavaScript, Python, Rust, TypeScript
LeetcodeHelp C++, Java, Python
Progiez C++, Java, Python
BigEggStudy C#
black-shadows C++, C++
bujosa Rust
chandansgowda Python
charles-wangkai Java
everthis JavaScript
fartem Ruby
FelixFan1122 C#
fengvyi C++
fpdjsns C++
fsq Python
halfrost Go
JoshCrozier JavaScript
keineahnung2345 C++
lkwq007 Python
MacJim C++
ruoru Rust
shreymehul C#
suxrobGM C#
trung-hn Python
varunu28 Java
vthwang Java
wisdompeak C++
yuanliu666 Kotlin
zfang399 C++
45 links | 30 authors | 10 languages

Videos

8 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

2 similar problems

Solved On The Same Day

3 medium 4 hard
8 solutions   August 10, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality