daily-temperatures

Difficulty: Medium · Topic: Stack · Practice it on parikshan: /practice/daily-temperatures/start

The story

A climate-data team at AccuWeather processes a year of daily highs for a city. For each day, they want to answer: "How many days until the next strictly warmer day?" The output feeds the "next heatwave countdown" widget on the city forecast page. If no warmer day ever comes, the answer is 0. They give you the array of temperatures; you return the array of waits.

That is daily-temperatures. The canonical monotonic stack problem. The same algorithm answers "next greater element" everywhere, from stock charting to chip-pin trace analysis.

What's actually being asked

Given an array T of n integers, return an array answer of length n where answer[i] is the number of days you have to wait after day i to get a strictly warmer day, or 0 if no such day exists.

"Strictly warmer" means T[j] > T[i]. Equal temperatures do not count.

The naive approach

Two nested loops: for each i, scan j > i until T[j] > T[i], record j - i. O(n^2). For n = 10^5, that is 10 billion. Times out.

The key insight

Maintain a stack of indices whose temperatures are in strictly decreasing order from bottom to top. Walk left to right. At each new index i:

While the stack is non-empty and T[stack.top()] < T[i]: the day at stack.top() has finally found its next warmer day (today, day i). Pop, and set answer[popped] = i - popped.
Push i.

After the loop, indices left on the stack never found a warmer day; their answers stay at the default 0.

The invariant: at any point, the stack contains all indices whose "next warmer day" is still unknown, and their temperatures decrease from bottom to top. When a hotter day arrives, it resolves all pending indices whose temperature is less than today's, possibly many at once.

Why the stack must be monotonic

If the stack were not decreasing, you would have to compare against multiple elements to find which ones today resolves, defeating the constant amortised cost. The decreasing invariant guarantees that resolution is a single contiguous pop sequence from the top: pop, pop, pop until you find one greater-or-equal. Each pop is one element resolved. Each element is pushed once and popped at most once. Total work: O(n).

Step-by-step approach

answer = [0] * n. stack = [] (will hold indices).
For i from 0 to n - 1:
- While stack is non-empty and T[stack[-1]] < T[i]:
  - j = stack.pop().
  - answer[j] = i - j.
- Push i onto stack.
Print answer space-separated.

Worked example

T = [73, 74, 75, 71, 69, 72, 76, 73]

i	T[i]	stack before	resolutions	stack after
0	73	[]	-	[0]
1	74	[0]	pop 0, answer[0]=1	[1]
2	75	[1]	pop 1, answer[1]=1	[2]
3	71	[2]	(71 < 75)	[2, 3]
4	69	[2, 3]	(69 < 71)	[2, 3, 4]
5	72	[2, 3, 4]	pop 4 (69<72), answer[4]=1; pop 3 (71<72), answer[3]=2	[2, 5]
6	76	[2, 5]	pop 5 (72<76), answer[5]=1; pop 2 (75<76), answer[2]=4	[6]
7	73	[6]	(73 < 76)	[6, 7]

End: indices 6 and 7 are still on the stack; their answers stay at 0.

Final answer: [1, 1, 4, 2, 1, 1, 0, 0].

Complexity

Time: O(n). Each index is pushed once and popped at most once.
Space: O(n) for the stack and answer array.

Common pitfalls

Storing temperatures, not indices, on the stack: you need the index to compute the gap. Always store indices in monotonic-stack problems where distances matter.
Using <= instead of < on the while-condition: <= would pop on equal temperatures, which is wrong (the spec demands strictly warmer). The wrong choice silently produces wrong answers on equal-value tests.
Walking right to left without adjusting the comparison: a right-to-left variant exists (decreasing stack from the right) but the comparison flips and the gap calculation changes. Pick one direction and stay with it.
Forgetting that elements left on the stack at end get 0: this is the spec's no-warmer-day default. Initialise answer to all zeros; do nothing for the unresolved indices.
Computing j - i instead of i - j: the gap is "days after i", so it must be positive, hence i - j where i is the resolving day and j is the earlier day.

Where this shows up in the enterprise

AccuWeather / Weather.com / Tomorrow.io: next-warmer-day widgets, drought-break forecasts.
NASDAQ / NYSE charting tools (TradingView, Bloomberg): next-higher-tick distance for momentum indicators.
Hardware design (Synopsys, Cadence): next-rising-edge analysis on chip simulation traces.
Audio / DSP (Avid Pro Tools, Logic): next-louder-sample distance for transient detection.
Genomics: next-higher-coverage position in a read pileup, for variant-calling preprocessing.
Cloud autoscaler post-mortems: next-higher-load timestamp after a capacity event.
SRE incident analysis at Datadog / PagerDuty: next-higher-severity event after a baseline-recovery moment.
Stripe Sigma / Snowflake analytics: "days until next higher revenue day" report.

The monotonic-stack pattern is the right tool for any "for each element, find the closest later element satisfying P" question.

Variants you'll see elsewhere

next-greater-element-i / ii: same pattern, return values not distances; circular variant.
next-greater-element-iii: lexicographic permutation, unrelated despite the name.
previous-smaller-element: reverse direction or flip comparison.
largest-rectangle-in-histogram: monotonic stack of indices with both next-smaller-right and next-smaller-left.
trapping-rain-water (stack variant): pop on increasing heights, compute trapped water per pop.
online-stock-span: same problem as a streaming API.
sum-of-subarray-minimums: contribution technique using next-smaller on both sides.

This problem is the gateway to roughly a dozen other classic problems. Master it once.

How parikshan turns this into a learning loop

The dynamic private tests on parikshan target:

A strictly increasing array (every answer is 1).
A strictly decreasing array (every answer is 0).
All equal values (every answer is 0 because strictly warmer is required).
The "warmer day arrives many positions later, resolving many" case (tests amortised correctness).
The single-element array (answer is [0]).
Large n near the constraint cap (proves the O(n) stack approach).

If your code uses <= and fails the all-equal test, the verdict points at the line. The integrity-scored AI sparring partner is the place, in practice mode, to verbalise the monotonic-stack invariant ("strictly decreasing from bottom to top, popping resolves indices whose temperature was less than today's") before writing the code in exam mode.

In the AI-integrated workspace

When an agent writes "next greater" or "wait until X" code, your review:

Is the stack storing indices, not values? Distances require indices.
Is the while-condition comparison strict (<) or non-strict (<=)? Match the spec.
Are unresolved elements left with the default answer (here, 0)? Or does the agent fill them with an incorrect sentinel like -1 or n?
Is the algorithm O(n) amortised? An agent that pops with a for-loop instead of a while-loop reverts to O(n^2) silently.

The senior-engineer reflex: see "for each element, find the closest later element satisfying P" and immediately reach for a monotonic stack. Once that reflex is wired, code review for this pattern becomes mechanical: "is this an O(n) monotonic stack, or did you write O(n^2)?". parikshan exists to wire that reflex.

daily-temperatures is the foundational monotonic-stack problem. Every subsequent problem in this family (and there are many) reuses the exact same scaffold. Treat the practice session here as the moment the monotonic stack becomes a tool in your hands, not just a phrase you have read.