Daily Temperatures
Daily Temperatures: for each day, return how many days you must wait for a warmer temperature. Answer 0 for any day with no warmer day ahead.
- 1 <= temperatures.length <= 10⁵
- 30 <= temperatures[i] <= 100
Intuition
A day is waiting until something warmer arrives. Keep the unanswered days on a stack, coldest question on top. Each new temperature resolves every day it beats — pop them, record the gap — then joins the stack to wait its own turn. Each day is pushed once and popped once, so the whole thing is linear.
The phrase 'next greater element' — or any 'how far until something bigger/smaller' — is the monotonic-stack signature. Keep unresolved indices in sorted order and let each new value settle everything it dominates. The same machinery solves Next Greater Element, Largest Rectangle in Histogram, and Trapping Rain Water.
Approach
Before reading on: when a warm day arrives, how many earlier days does it answer at once? What order must those waiting days be in for the newest one to always be checked first? Aim for O(n).
Why the brute force wastes work
For each day, scanning forward until a warmer temperature appears is correct but O(n²) — on the 10⁵-day inputs allowed, that is billions of comparisons. Worse, it re-reads the same stretch repeatedly: a long cold spell is walked over again for every day inside it. The insight is that those re-scans are answering the same question, so the work should be shared rather than repeated.
A monotonic stack of unresolved days
Hold a stack of indices whose answers are still unknown, and keep their temperatures decreasing from bottom to top. When day i arrives, compare it with the temperature at the top index. If today is warmer, that day's wait is over — pop it and write i - popped into the answer. Repeat while the top is still colder, because one warm day can settle a whole run of colder ones. Then push i, since its own answer is now pending. The decreasing order is what makes the top always the most urgent question.
Why every index is touched twice at most
Each index is pushed exactly once and popped at most once, so the total pop work across the entire run is bounded by n — even though a single iteration may pop many entries. That amortised argument is what turns a nested-looking loop into O(n) time. Anything still on the stack when the scan ends never found a warmer day, so those answers stay at their initialised value of 0, which is exactly the required output.
Solution & live demo
Common pitfalls
Storing temperatures instead of indices
stack.append(temp)
stack.append(i)
The answer is a distance between days, so you need the index to compute i - prev. With only temperatures on the stack there is no way to recover where the waiting day was.
Using if instead of while
if stack and temperatures[stack[-1]] < temp:
...while stack and temperatures[stack[-1]] < temp:
...One warm day can end the wait for many colder days at once. An if resolves only the top and leaves the rest stranded with a wrong answer of 0 — on [70,60,50,80] it settles day 2 but never days 0 and 1.
Popping on equal temperatures
while stack and temperatures[stack[-1]] <= temp:
while stack and temperatures[stack[-1]] < temp:
The problem asks for a strictly warmer day. With <=, a repeated temperature resolves the earlier day and reports a wait of 1 when the correct answer looks further ahead.
Edge cases
Nothing is ever popped, every index remains on the stack, and all answers stay 0.
Each day pops exactly one predecessor, so every answer is 1 except the last, which is 0.
The comparison is strict (>), so an equal day does not count as warmer and the earlier day keeps waiting.
It is pushed and never resolved, so the answer is [0].