Daily Temperatures
For each day, compute how far away the next warmer temperature appears.
Problem Summary
Original task summary for this archive page. The official LeetCode prompt is linked in the header instead of being mirrored here.
For each day, determine how many days you must wait until a warmer temperature appears. If no warmer day exists, the answer for that position is zero.
This is not just a comparison problem. Each day is waiting for its next greater element to the right.
Recognition Pattern
How to notice the underlying interview pattern before writing code.
This is a monotonic stack problem.
In interviews, recognize it when:
each position wants the next greater or smaller value
the answer depends on the nearest qualifying element to the left or right
a brute-force scan would repeatedly revisit the same unresolved elements
Key Idea
The main invariant or observation that makes the clean solution work.
Store indices of days that have not found a warmer future day yet.
Keep the stack in decreasing temperature order. When a new temperature arrives:
while it is warmer than the day on top of the stack, resolve that older day
the distance is the current index minus the stored index
then push the current day as a new unresolved candidate
Each index is pushed once and popped once, so the total work stays linear.
Step-by-step Reasoning
How to move from the obvious brute-force idea to the interview-ready solution.
The brute-force solution checks every later day for every index, which costs \(O(n^2)\).
The wasted work comes from repeatedly scanning over days that are still unresolved. A stack fixes that by keeping exactly those unresolved candidates in one place.
The decreasing-order invariant is what makes the stack useful. If the current day is not warmer than the top, then it is also not warm enough to resolve anything below that top, so you can stop immediately.
That is the main monotonic-stack pattern: keep a structural invariant so each new element resolves as much old work as it can, and no more.
Complexity
Time and memory costs for the implementation shown below.
Time: \(O(n)\)
Space: \(O(n)\)
C++ Solution
The exact repository source used for this LeetCode solution page.
#include <stack>
#include <vector>
class Solution {
public:
std::vector<int> dailyTemperatures(std::vector<int>& temperatures) {
std::vector<int> answer(temperatures.size(), 0);
std::stack<int> pendingIndices;
for (int index = 0; index < static_cast<int>(temperatures.size()); ++index) {
while (!pendingIndices.empty() && temperatures[index] > temperatures[pendingIndices.top()]) {
const int previousIndex = pendingIndices.top();
pendingIndices.pop();
answer[previousIndex] = index - previousIndex;
}
pendingIndices.push(index);
}
return answer;
}
};
Common Pitfalls
Real implementation mistakes that show up often in interviews and submissions.
Store indices, not temperatures. You need indices both for comparison and for computing distances.
The comparison must be strict. Equal temperatures do not count as warmer days.
Initialize the answer array with zeros so unresolved days naturally keep the correct default.
Variants / Follow-ups
Nearby problems and the next generalization to learn once this pattern is stable.
This same pattern appears in Next Greater Element, Next Greater Element II, Stock Span, and many histogram or range-boundary problems.
The transferable skill is recognizing when unresolved positions should be stored in a monotone order instead of re-scanned later.
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.