ASAPUtils
The signal
“For each element, find the next greater element and report the distance.” Brute force scans the same future days repeatedly. Let each new warmer day answer the unresolved colder days behind it.
Approach ladder
1. Scan forward from every day — O(n²)
Correct, but a long decreasing sequence repeats almost the whole remaining scan from every index.
2. Decreasing stack of unresolved indices — O(n)
The stack holds days whose answer is unknown. Their temperatures are monotonically decreasing from bottom to top. When today’s temperature is greater than the top’s temperature, today is the first warmer day for that top, so pop and resolve it. Repeat until the invariant is restored.
vector<int> dailyTemperatures(vector<int>& temperatures) {
vector<int> answer(temperatures.size(), 0), st;
for (int i = 0; i < (int)temperatures.size(); i++) {
while (!st.empty() && temperatures[st.back()] < temperatures[i]) {
int day = st.back(); st.pop_back();
answer[day] = i - day;
}
st.push_back(i);
}
return answer;
}
function dailyTemperatures(temperatures) {
const answer = new Array(temperatures.length).fill(0);
const stack = [];
for (let i = 0; i < temperatures.length; i++) {
while (stack.length && temperatures[stack.at(-1)] < temperatures[i]) {
const day = stack.pop();
answer[day] = i - day;
}
stack.push(i);
}
return answer;
}
Why the answer is the first warmer day
If an earlier warmer day existed, it would already have popped this index. The index survived on the stack precisely because every day seen since was less than or equal to it. Therefore the day that finally pops it is the nearest valid day, not merely some valid day.
Complexity
O(n) time by the push-once/pop-once amortised argument. O(n) stack space in a decreasing input.
Traps
- Storing temperatures instead of indices, then being unable to compute the distance.
- Using
<=when the question requires warmer, not warmer-or-equal. - Filling unresolved days separately. Initialising the answer with zeros handles them.
- Calling the nested loop O(n²) without counting lifetime pushes and pops.
Blank re-solve prompt
Return the wait until the next strictly warmer day. Before coding, state what the stack contains and why its temperatures are decreasing.