Daily Temperatures
For each day, how long until it gets warmer — the monotonic stack, and why it is linear despite the nested loop
Problem Statement
Given an array of daily temperatures, return an array where answer[i] is the number of days you must wait after day i for a warmer temperature. If no warmer day ever comes, put 0.
Input: temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1, 1, 4, 2, 1, 1, 0, 0]
Day 0 (73): day 1 is 74, warmer → wait 1
Day 2 (75): next warmer is day 6 (76) → wait 4
Day 6 (76): nothing warmer follows → 0Intuition
The brute force is: for each day, scan forward until you find something warmer. O(n²), and on a long decreasing run it does an enormous amount of repeated scanning.
Look at what that repetition is doing. Scanning forward from day 3 walks over days 4, 5, 6. Scanning from day 4 walks over 5, 6 again. The same days are re-examined over and over.
The key insight
Turn the question inside out. Instead of each day searching forward for its answer, let each new day look backward and resolve everyone who was waiting for it.
Keep a stack of days that are still waiting. When a warmer day arrives, it settles every waiting day it beats — all at once.
Why the stack is monotonic
Here is the property that makes it work.
If day a comes before day b and temp[a] <= temp[b], then day a can be discarded from consideration the moment b arrives — because any future day warm enough to settle a would have already settled b first.
Put another way
A day only stays on the stack while it is colder than everything after it that is still pending. So the stack holds temperatures in decreasing order from bottom to top.
That is what "monotonic stack" means: the stack is kept sorted by construction, and anything violating the order is popped off.
Stack (bottom → top) holds indices of days still waiting:
75 ← colder days sit on top
71
69 ← top: coldest, most recently addedWhen day 5 (72°) arrives, it pops 69 and 71 — both are settled — but stops at 75, which is still warmer and keeps waiting.
Why this is O(n), despite the nested loop
The while inside the for looks quadratic. It is not.
The counting argument
Each day is pushed exactly once and popped at most once. That is 2n stack operations across the whole run, no matter how the inner loop is distributed.
Some days pop nothing; one day might pop twenty. The total is still bounded by n.
This is called amortised analysis, and it is the same reasoning that makes the set version of a sliding window linear.
The real-world version
People queue at a counter, each waiting for someone taller than them to walk past. They stand in order of decreasing height, so the shortest is always at the front.
When a tall person walks by, everyone shorter than them is served immediately and leaves. The tall person then joins the queue to wait for someone taller still.
Approach
Start with an answer array of zeros
Zero is already the correct answer for any day that never warms up, so days left on the stack at the end need no special handling.
Keep a stack of indices, not temperatures
You need the index to compute the waiting time, and the index gives you the temperature anyway. Storing temperatures alone loses the position.
For each day, pop every colder day still waiting
While the stack is non-empty and today is warmer than the day on top, pop it and record answer[popped] = today - popped.
Push today
Today now waits for its own warmer day.
Watch it run
Solution
def daily_temperatures(temperatures: list[int]) -> list[int]:
"""For each day, days until a warmer one. 0 if none follows."""
n = len(temperatures)
# 0 is already correct for days that never warm up.
answer = [0] * n
# Indices of days still waiting, temperatures decreasing bottom to top.
stack: list[int] = []
for today, temp in enumerate(temperatures):
# Today settles every colder day still waiting.
while stack and temperatures[stack[-1]] < temp:
earlier = stack.pop()
answer[earlier] = today - earlier
stack.append(today)
# Anything left never warmed up — already 0.
return answerThree details that decide correctness
Store indices, not temperatures. Without the index you cannot compute today - earlier, and you cannot write into the right slot of answer.
Use < not <=. The problem asks for a strictly warmer day. With <=, an equal temperature would wrongly settle the earlier day. Check [73, 73]: the answer is [0, 0], not [1, 0].
Check the stack is non-empty first. Both languages short-circuit left to right, so stack and temperatures[stack[-1]] < temp is safe. Reversing the order reads from an empty stack — IndexError in Python, undefined in TypeScript.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(n)
- Time — the outer loop runs
ntimes. The innerwhilelooks like it could multiply that, but each index is pushed once and popped once, so all inner iterations together total at mostn. That givesO(n)overall. - Space — the stack holds at most
nindices, which happens when temperatures strictly decrease and nothing is ever settled. The output array is not usually counted, since it is required by the problem.
Edge Cases
Related Problems
- Valid Parentheses — a stack for nesting rather than ordering
- Min Stack — a stack carrying extra state alongside each value
- Trapping Rain Water — solvable with this same monotonic stack, as well as with two pointers
- Stacks & Queues — recognising which one a problem needs