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;
}
};
Difficulty
and has an acceptance rate of about 69% (2+ million submissions).
Typical patterns to solve this problem:
- Array
- Monotonic Stack
- Stack
AI Disclaimer
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.
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 thelastarray. - 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.
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.
Code Quality
Complexity Analysis
Other Solutions
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++ |
Videos
Similar Problems
- problem 496: Next Greater Element I
- problem 901: Online Stock Span
Solved On The Same Day
- problem 19: Remove Nth Node From End of List
- problem 61: Rotate List
- problem 208: Implement Trie (Prefix Tree)
- problem 23: Merge k Sorted Lists
- problem 214: Shortest Palindrome
- problem 1316: Distinct Echo Substrings
- problem 1392: Longest Happy Prefix
Extra
- 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