Daily Temperatures
Problem
temperatures. For every day
i, report how many days you must wait until a strictly warmer day arrives.
If no warmer day ever comes, report 0 for that day.[73,74,75,71,69,72,76,73]Output[1,1,4,2,1,1,0,0][30,40,50,60]Output[1,1,1,0][30,60,90]Output[1,1,0]1 ≤ n ≤ 105 · 30 ≤ temperatures[i] ≤ 100
Try it yourself
class Solution {
public int[] dailyTemperatures(int[] T) {
}
}
Instinct Each element needs its nearest bigger or smaller neighbour (next warmer day, span, widest bar) - keep a sorted stack of waiting indices.
Memory hack Tall people block the view - a newcomer kicks out everyone shorter waiting behind, and each kicked-out person just found their answer.
Open the Monotonic Stack guide →Approaches
Brute ForceScan Forward from Every Day
O(n2)Space O(1) extraFor each day i, walk j = i+1, i+2, ... and stop at the
first T[j] > T[i]; the answer is j - i. A strictly
decreasing input forces every scan to run to the end.
public int[] dailyTemperatures(int[] T) { int n = T.length; int[] result = new int[n]; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (T[j] > T[i]) { result[i] = j - i; break; } } } return result; }
Trivially correct, but ~5·109 steps for n = 105.
BetterBackward Scan + Next-Index per Temperature
O(n · W)Space O(W)Temperatures live in a tiny range (W = 71 values). Walk from the right and keep
next[t] = nearest index to the right holding temperature t.
For day i, the answer is the smallest next[t] over all
t > T[i].
public int[] dailyTemperatures(int[] T) { int n = T.length; int[] result = new int[n]; int[] next = new int[101]; Arrays.fill(next, Integer.MAX_VALUE); for (int i = n - 1; i >= 0; i--) { int warmer = Integer.MAX_VALUE; for (int t = T[i] + 1; t <= 100; t++) warmer = Math.min(warmer, next[t]); if (warmer != Integer.MAX_VALUE) result[i] = warmer - i; next[T[i]] = i; } return result; }
Linear in n, but each day still scans up to 70 warmer temperatures.
OptimalMonotonic Decreasing Stack of Indices
O(n)Space O(n)The stack holds indices of unresolved days, temperatures decreasing from
bottom to top. When day i is warmer than the top, the top's answer is
i - top; pop and repeat. Each index is pushed and popped at most once.
public int[] dailyTemperatures(int[] T) { int n = T.length; int[] result = new int[n]; Deque<Integer> stack = new ArrayDeque<>(); // indices still waiting for (int i = 0; i < n; i++) { while (!stack.isEmpty() && T[i] > T[stack.peek()]) { int idx = stack.pop(); result[idx] = i - idx; } stack.push(i); } return result; }
Dry run[73,74,75,71,69,72,76,73]
- i=17374i s75716972767374>73 → ans[0]=1
- i=2737475i s716972767375>74 → ans[1]=1
- i=4737475s71s69i s727673push 71, 69
- i=5737475s716972i s7673ans[4]=1, ans[3]=2
- i=673747571697276i s73ans[5]=1, ans[2]=4
- i=773747571697276s73i sleft on stack → 0 ✔
Linear time regardless of value range — the expected answer.
j += ans[j] to skip
days already known to be colder.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Scan Forward from Every Day | O(n2) | O(1) extra |
| Better | Backward Scan + Next-Index per Temperature | O(n · W) | O(W) |
| Optimal | Monotonic Decreasing Stack of Indices | O(n) | O(n) |
- Pushing temperatures instead of indices — you need positions to compute distances.
- Using
>=in the pop condition — equal temperature is not warmer. - Using
java.util.Stack(synchronized, slower) instead ofArrayDeque.
- Name the pattern out loud: “next greater element → monotonic stack”.
- Argue O(n) by amortisation: every index is pushed once and popped at most once.
- Mention that leftover stack entries default to 0 — no extra pass needed.