Monotonic Stack — Daily Temperatures
↗ LeetCode: Daily Temperatures · Medium · pattern chapter →
Given temps, return answer where answer[i] is the number of days until a warmer temperature (or 0 if none).
Example 1 — temps=[73,74,75,71,69,72,76,73] → [1,1,4,2,1,1,0,0]Example 2 — temps=[30,40,50,60] → [1,1,1,0]
Constraints — 1 ≤ n ≤ 10⁵; 30 ≤ temps[i] ≤ 100. Brute searches forward for the next warmer day per element — O(n²) = 10¹⁰ ops at n=10⁵ (TLE). Monotonic decreasing stack visits each index once → O(n) = 10⁵ ops with amortised O(1) per push/pop.
Interview timer00:00
Approach 1 — Brute force (nested scan)
Intuition. For each day i, scan forward until a warmer day.
int[] dailyTemperaturesBrute(int[] t) {
int n = t.length;
int[] ans = new int[n];
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (t[j] > t[i]) { ans[i] = j - i; break; }
return ans;
}Complexity — Time O(n²) worst case (strictly decreasing input); Space O(1) aside from output.
Approach 2 — Right-to-left with next-greater cache
Insight from brute. After computing ans[i+1], many days beyond i+1 are known — we can jump over them.
Walk right-to-left. For day i, start at j = i+1. If t[j] ≤ t[i], jump forward by ans[j] (the known distance to a warmer day). Repeat until a warmer day is found or we fall off.
int[] dailyTemperaturesRTL(int[] t) {
int n = t.length;
int[] ans = new int[n];
for (int i = n - 2; i >= 0; i--) {
int j = i + 1;
while (j < n && t[j] <= t[i]) {
if (ans[j] == 0) { j = n; break; }
j += ans[j];
}
if (j < n) ans[i] = j - i;
}
return ans;
}Complexity — Time O(n) amortized (jumps skip regions of ≤); Space O(1) output only.
Slick but non-obvious. The stack version below is easier to reason about — and interviewer-preferred.
Approach 3 — Monotonic decreasing stack (indices)
Insight from RTL cache. The RTL solution is really doing a monotonic decreasing traversal from the right. A stack-based left-to-right pass captures the same idea more explicitly.
Push indices onto a decreasing stack. When t[i] beats the top, that top's answer is i − top. Pop and repeat.
Trap. Store indices, not temperatures — you need i - top for the answer.
int[] dailyTemperatures(int[] t) {
int n = t.length;
int[] ans = new int[n];
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && t[stack.peek()] < t[i]) {
int idx = stack.pop();
ans[idx] = i - idx;
}
stack.push(i);
}
return ans;
}Complexity — Time O(n) (each index pushed + popped at most once); Space O(n) for the stack.
Try it yourself
Complexity summary
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n²) | O(1) |
| RTL with cache jump | O(n) amortized | O(1) |
| Monotonic stack | O(n) | O(n) |
When to use which
- Cold interview → brute → stack. RTL is smart but hard to explain fast.
- "Next greater element" family → always monotonic stack. Once you see the pattern (
while stack.top < current: pop and record), the whole family is solved by adjusting the comparator.
Related problems (same ladder applies)
- Next Greater Element II — circular array; walk 2n times,
i%n - Online Stock Span — same skeleton, streaming input
- Sum of Subarray Minimums — monotonic stack + contribution technique
- Largest Rectangle in Histogram — closest-smaller-both-sides via one stack