DSA-044 · Monotonic unresolved-index stack
Daily Temperatures
Intermediate · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 9844 deterministic checks. Learner drafts are not executed.
Understand the problem
For every day, return how many days must pass until the first strictly warmer temperature. Return zero at positions with no later warmer day.
- Non-null int[] of 0–100,000 signed int temperatures. Comparisons are ordinal; no restricted weather range is assumed.
- Return a new int[] of the same length. Equal temperature is not warmer. The answer is a distance, not an index or temperature difference.
- Preserve input. Each positive answer must identify the nearest later strictly greater value.
Examples
Input:
[73,74,75,71,69,72,76,73]
Output:[1,1,4,2,1,1,0,0]Day 2 waits until day 6, while days 6 and 7 have no warmer future day.
Input:
[70,70,71]
Output:[2,1,0]Equal temperatures remain unresolved until 71 arrives.
Before you start
- Stack push/pop and index distances
- Strict comparison and amortized analysis
Recognize the structure
A new larger value can answer several still-unresolved earlier positions. Keep those indices in a stack ordered by non-increasing temperature. This is next-greater-to-the-right, not a maximum-so-far query.
Try before revealing
Hint 1
Keep earlier positions whose answer is still unknown.
Hint 2
Which unresolved positions can today answer?
Hint 3
Pop every cooler top, assign its distance, then push today.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Search each suffix
For day i, scan j=i+1 onward until temperatures[j]>temperatures[i], store j-i, and stop. For [3,2,4], day 0 waits two steps and day 1 waits one. In a decreasing array every suffix is exhausted, giving O(n²) time; the answer array costs O(n) and other workspace is O(1).
Improve the baseline
Retain only unanswered days
Push indices, so the required distance can be computed when an answer arrives. The stack stores unresolved candidates, not final temperatures alone.
Resolve smaller stack tops
While today is strictly warmer than the top’s temperature, pop that earlier index and set its wait to day-earlier.
Push today after resolving
Remaining temperatures are at least today’s, so appending today preserves non-increasing order. Equality stays unresolved because only a strictly warmer day qualifies.
Why it is correct
Initialize
The empty stack contains every unresolved day of the empty prefix, and all output entries start at zero.
Preserve
A popped index has not encountered a warmer day before today; otherwise it would already have been popped. Thus today is its first warmer day. After smaller tops are removed, the remaining top is no cooler than today, preserving non-increasing temperature order when today is pushed.
Finish
Every positive result was assigned at its first valid day. Remaining indices never encounter a warmer day and correctly retain zero. Every index is pushed once and popped at most once.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
import java.util.ArrayDeque;
import java.util.Deque;
public final class Solution {
public static int[] dailyTemperatures(int[] temperatures) {
int[] answer = new int[temperatures.length];
Deque<Integer> unresolved = new ArrayDeque<>();
for (int day = 0; day < temperatures.length; day++) {
while (!unresolved.isEmpty() && temperatures[day] > temperatures[unresolved.peek()]) {
int earlier = unresolved.pop();
answer[earlier] = day - earlier;
}
unresolved.push(day);
}
return answer;
}
public static int[] baseline(int[] temperatures) {
int[] answer = new int[temperatures.length];
for (int i = 0; i < temperatures.length; i++)
for (int j = i + 1; j < temperatures.length; j++)
if (temperatures[j] > temperatures[i]) { answer[i] = j - i; break; }
return answer;
}
}
Read the meaningful blocks
Store indices
Values alone lose both original positions and waiting distances.
Use a strict greater-than test
Changing > to ≥ incorrectly resolves equal temperatures.
Pop all newly answered days
One warm day may settle several earlier candidates; an if cannot replace the while.
Complexity
O(n) total time by aggregate accounting: each index enters and leaves the stack at most once, despite nested syntax. O(n) auxiliary stack space in the decreasing/equal case.
The returned answer is separately O(n) output storage. Baseline uses O(n²) time, O(1) auxiliary space beyond that output.
Exact-state walkthroughs
Reveal normal and boundary traces
One day resolves several
Input: [3,2,1,4] · Result: [3,2,1,0]
Step 1 of 9: No day has yet been processed.
All retained indices are unresolved.
Empty at this step.
| Variable | Value |
|---|---|
| temperatures | [3,2,1,4] |
| stackBottomToTop | [] |
| answer | [0,0,0,0] |
See the affected Java block
1 import java.util.ArrayDeque; 2 import java.util.Deque; 3 4 public final class Solution { 5 public static int[] dailyTemperatures(int[] temperatures) { 6 int[] answer = new int[temperatures.length]; 7 Deque<Integer> unresolved = new ArrayDeque<>(); 8 for (int day = 0; day < temperatures.length; day++) { 9 while (!unresolved.isEmpty() && temperatures[day] > temperatures[unresolved.peek()]) { 10 int earlier = unresolved.pop(); 11 answer[earlier] = day - earlier; 12 } 13 unresolved.push(day); 14 } 15 return answer; 16 } 17 18 public static int[] baseline(int[] temperatures) { 19 int[] answer = new int[temperatures.length]; 20 for (int i = 0; i < temperatures.length; i++) 21 for (int j = i + 1; j < temperatures.length; j++) 22 if (temperatures[j] > temperatures[i]) { answer[i] = j - i; break; } 23 return answer; 24 } 25 } 26
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- No day has yet been processed.
All retained indices are unresolved.
- temperatures
[3,2,1,4]- stackBottomToTop
[]- answer
[0,0,0,0]
- Retain today as unresolved.
Stack temperatures are non-increasing from bottom to top; equal values remain.
- day
0- stackBottomToTop
[0]- answer
[0,0,0,0]
- Retain today as unresolved.
Stack temperatures are non-increasing from bottom to top; equal values remain.
- day
1- stackBottomToTop
[0,1]- answer
[0,0,0,0]
- Retain today as unresolved.
Stack temperatures are non-increasing from bottom to top; equal values remain.
- day
2- stackBottomToTop
[0,1,2]- answer
[0,0,0,0]
- Today is the first warmer day for this index.
No earlier warmer day passed without resolving the popped position.
- day
3- earlier
2- stackBottomToTop
[0,1]- answer
[0,0,1,0]
- Today is the first warmer day for this index.
No earlier warmer day passed without resolving the popped position.
- day
3- earlier
1- stackBottomToTop
[0]- answer
[0,2,1,0]
- Today is the first warmer day for this index.
No earlier warmer day passed without resolving the popped position.
- day
3- earlier
0- stackBottomToTop
[]- answer
[3,2,1,0]
- Retain today as unresolved.
Stack temperatures are non-increasing from bottom to top; equal values remain.
- day
3- stackBottomToTop
[3]- answer
[3,2,1,0]
- Return the contract result.
The final state satisfies the requested output contract.
- result
[3,2,1,0]
Equal temperatures wait
Input: [70,70,71] · Result: [2,1,0]
Step 1 of 7: No day has yet been processed.
All retained indices are unresolved.
Empty at this step.
| Variable | Value |
|---|---|
| temperatures | [70,70,71] |
| stackBottomToTop | [] |
| answer | [0,0,0] |
See the affected Java block
1 import java.util.ArrayDeque; 2 import java.util.Deque; 3 4 public final class Solution { 5 public static int[] dailyTemperatures(int[] temperatures) { 6 int[] answer = new int[temperatures.length]; 7 Deque<Integer> unresolved = new ArrayDeque<>(); 8 for (int day = 0; day < temperatures.length; day++) { 9 while (!unresolved.isEmpty() && temperatures[day] > temperatures[unresolved.peek()]) { 10 int earlier = unresolved.pop(); 11 answer[earlier] = day - earlier; 12 } 13 unresolved.push(day); 14 } 15 return answer; 16 } 17 18 public static int[] baseline(int[] temperatures) { 19 int[] answer = new int[temperatures.length]; 20 for (int i = 0; i < temperatures.length; i++) 21 for (int j = i + 1; j < temperatures.length; j++) 22 if (temperatures[j] > temperatures[i]) { answer[i] = j - i; break; } 23 return answer; 24 } 25 } 26
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- No day has yet been processed.
All retained indices are unresolved.
- temperatures
[70,70,71]- stackBottomToTop
[]- answer
[0,0,0]
- Retain today as unresolved.
Stack temperatures are non-increasing from bottom to top; equal values remain.
- day
0- stackBottomToTop
[0]- answer
[0,0,0]
- Retain today as unresolved.
Stack temperatures are non-increasing from bottom to top; equal values remain.
- day
1- stackBottomToTop
[0,1]- answer
[0,0,0]
- Today is the first warmer day for this index.
No earlier warmer day passed without resolving the popped position.
- day
2- earlier
1- stackBottomToTop
[0]- answer
[0,1,0]
- Today is the first warmer day for this index.
No earlier warmer day passed without resolving the popped position.
- day
2- earlier
0- stackBottomToTop
[]- answer
[2,1,0]
- Retain today as unresolved.
Stack temperatures are non-increasing from bottom to top; equal values remain.
- day
2- stackBottomToTop
[2]- answer
[2,1,0]
- Return the contract result.
The final state satisfies the requested output contract.
- result
[2,1,0]
Test the contract
Input:
[]
Output:[]Empty output.
Input:
[9]
Output:[0]No future day.
Input:
[3,2,1]
Output:[0,0,0]Worst-case retained stack.
Input:
[1,2,3]
Output:[1,1,0]Immediate answers.
Common mistakes and counterexamples
Resolve equal values
Counterexample: [70,70] should be [0,0].
Use strict >.
Pop just one earlier day
Counterexample: [3,2,1,4] resolves three earlier days at once.
Repeat while the top is cooler.
Return temperature difference
Counterexample: [30,80] waits one day, not fifty.
Subtract indices.
Follow-ups
Make the temperatures circular.
Scan a doubled index range but push each original index only once. Bound valid distances and keep equality unresolved; do not accidentally let a position answer itself.
Find the next greater-or-equal value.
Change the comparison and restate the stack invariant; equality handling changes which positions can be removed.
Maintain stock span online.
Store value/span pairs and aggregate spans while popping dominated previous days. The direction of the query and the meaning of an entry differ from future waiting distances.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 104/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.