25.Daily Temperatures
Problem
Given an array temperatures of daily temperatures, return an array answer where answer[i] is the number of days you must wait after day i to get a strictly warmer temperature. If no future day is warmer, answer[i] = 0.
Examples
Input: temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1, 1, 4, 2, 1, 1, 0, 0]
Explanation: Day 2 (75) waits until day 6 (76) → 4 days.
Day 3 (71) waits until day 5 (72) → 2 days.Input: temperatures = [30, 40, 50, 60]
Output: [1, 1, 1, 0]Input: temperatures = [30, 60, 90]
Output: [1, 1, 0]Constraints
1 <= temperatures.length <= 10^530 <= temperatures[i] <= 100
💡 Key Insight
This is a next greater element problem. Days that are still waiting for a warmer day always form a decreasing sequence of temperatures (if a later day were warmer, the earlier one would already be resolved). Keep those waiting days on a stack: each new day pops — and answers — every waiting day colder than itself. Every index is pushed and popped once, so the whole thing is O(n).
Brute Force
TimeO(n²)SpaceO(1)Intuition
For each day, look forward one day at a time until a warmer temperature appears.
Algorithm
- For each
i:- For
jfromi + 1ton - 1: iftemperatures[j] > temperatures[i], setanswer[i] = j - iand break.
- For
- Return
answer(unresolved entries stay0).
Visualization
temps = [73, 74, 75, 71, 69, 72, 76, 73]
i=2 (75): 71 ✗, 69 ✗, 72 ✗, 76 ✓ → 6 - 2 = 4
i=3 (71): 69 ✗, 72 ✓ → 5 - 3 = 2Code
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] answer = new int[n];
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (temperatures[j] > temperatures[i]) {
answer[i] = j - i; // first warmer day
break;
}
}
}
return answer;
}
}Complexity
- Time: O(n²) — a strictly decreasing input makes every day scan to the end.
- Space: O(1) — excluding the output array.
Monotonic Decreasing Stack
TimeO(n)SpaceO(n)Intuition
Walk forward and keep a stack of indices of days still waiting. Their temperatures are decreasing from bottom to top. When today is warmer than the top, today is that day's answer — pop it and record the distance, then check the next one. Finally push today; it waits too.
Algorithm
- Empty stack of indices.
- For each
i:- While the stack is non-empty and
temperatures[i] > temperatures[stack.peek()]:j = pop(),answer[j] = i - j. - Push
i.
- While the stack is non-empty and
- Return
answer.
Dry Run
flowchart TD
A["i0 73: stack [73]"] --> B["i1 74: pop 73 → ans0 = 1<br/>stack [74]"]
B --> C["i2 75: pop 74 → ans1 = 1<br/>stack [75]"]
C --> D["i3 71, i4 69: push<br/>stack [75, 71, 69]"]
D --> E["i5 72: pop 69 → ans4 = 1<br/>pop 71 → ans3 = 2<br/>stack [75, 72]"]
E --> F["i6 76: pop 72 → ans5 = 1<br/>pop 75 → ans2 = 4<br/>stack [76]"]
F --> G["i7 73: push → stack [76, 73]<br/>leftovers keep 0"](The stack stores indices; temperatures are shown for readability.)
Code
import java.util.ArrayDeque;
import java.util.Deque;
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] answer = new int[n];
Deque<Integer> stack = new ArrayDeque<>(); // indices still waiting
for (int i = 0; i < n; i++) {
// today resolves every colder day waiting on the stack
while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
int j = stack.pop();
answer[j] = i - j;
}
stack.push(i);
}
return answer;
}
}Complexity
- Time: O(n) — each index is pushed once and popped at most once.
- Space: O(n) — a strictly decreasing input keeps every index on the stack.
Backward Pass with JumpsOptimal
TimeO(n) amortizedSpaceO(1)Intuition
Go from right to left, reusing answers already computed. To find the next warmer day for i, start at j = i + 1. If temperatures[j] is not warmer, there is no point checking the days between j and j's own next warmer day — they are all <= temperatures[j] <= temperatures[i]. So jump j += answer[j]. If answer[j] == 0, nothing warmer than j exists, so nothing warmer than i either. No stack needed.
Algorithm
answer[n-1] = 0.- For
ifromn - 2down to0:j = i + 1.- While
temperatures[j] <= temperatures[i]:- If
answer[j] == 0, setj = -1and stop (no warmer day). - Else
j += answer[j].
- If
- If
j != -1,answer[i] = j - i.
- Return
answer.
Dry Run
temps = [73, 74, 75, 71, 69, 72, 76, 73]
index 0 1 2 3 4 5 6 7
i=6 (76): j=7 (73) ≤ 76, answer[7]=0 → none → 0
i=5 (72): j=6 (76) > 72 → 1
i=4 (69): j=5 (72) > 69 → 1
i=3 (71): j=4 (69) ≤ 71, jump +1 → j=5 (72) > 71 → 2
i=2 (75): j=3 (71) ≤ 75, jump +2 → j=5 (72) ≤ 75,
jump +1 → j=6 (76) > 75 → 4
i=1 (74): j=2 (75) > 74 → 1
i=0 (73): j=1 (74) > 73 → 1Code
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] answer = new int[n];
for (int i = n - 2; i >= 0; i--) {
int j = i + 1;
while (temperatures[j] <= temperatures[i]) {
if (answer[j] == 0) {
j = -1; // nothing warmer than day j, so nothing for day i
break;
}
j += answer[j]; // skip days that are colder than day j
}
if (j != -1) {
answer[i] = j - i;
}
}
return answer;
}
}Complexity
- Time: O(n) amortized — the jump chains follow the same "next greater" links a stack would pop, so total jumps are linear.
- Space: O(1) — only the output array is used.
Complexity Comparison
| Approach | Time | Space (excl. output) |
|---|---|---|
| Brute Force | O(n²) | O(1) |
| Monotonic Stack | O(n) | O(n) |
| Backward Jumps | O(n) | O(1) |
Common Pitfalls
- Using
>=instead of>when popping — an equal temperature is not warmer. - Pushing temperatures instead of indices onto the stack; you need the index to compute the distance
i - j. - In the backward pass, looping forever when
answer[j] == 0— that means "no warmer day", so stop instead of adding0. - Forgetting that days left on the stack at the end must stay
0(Java arrays default to0, so no extra work is needed).