Daily Temperatures
For each day, count how many days you have to wait for a warmer one.
- Monotonic stack
- Next greater element
Before this, know: What a stack is (push, pop, peek), Arrays and indexes
You get a list temperatures, one number per day. For each day, answer the
question: “how many days until it’s warmer than today?” If no warmer day ever
comes, the answer for that day is 0. Return all the answers as a list.
Take temperatures = [73, 71, 69, 72, 76]. Day 0 is 73°. The next day warmer than
73° is day 4 (76°), so day 0 waits 4 days. Day 2 is 69°, and the very next day
(72°) is warmer, so it waits 1 day.
So the answer is [4, 2, 1, 1, 0]. Rules that matter:
- “Warmer” means strictly warmer. Equal doesn’t count.
- There can be up to 100,000 days, with temperatures between 30 and 100.
Here is the key observation. When a new day arrives, the days still waiting for a warmer day always have temperatures that go down as you move to the most recent one. Why? If an older waiting day were colder than a newer one, the newer one would already have been its warmer day, and it would have stopped waiting.
Pause and think
Check the most recent waiting day first: day 2 (69°). 72 > 69, so day 2’s answer is 3 − 2 = 1. Next most recent: day 1 (71°). 72 > 71, so its answer is 3 − 1 = 2. Then day 0 (73°): 72 is not warmer, so day 0 keeps waiting.
And we can stop there: anything older than day 0 would be even warmer than 73°. Most recent first, and stop at the first “no”: that’s a stack.
For each day, walk forward one day at a time until a warmer day shows up. The distance is the answer. If we hit the end, the answer stays 0.
Brute force: look forward from every day
temperatures = [73, 71, 69, 72, 76]
- 00
- 01
- 02
- 03
- 04
- Day i
- Later day j
- First warmer day
- Answer known
Day 0 (73°): walk forward, one day at a time, until we find a warmer day.
Which line is running?
function dailyTemperatures(temperatures) { const n = temperatures.length; const answer = new Array(n).fill(0);Running now: for (let i = 0; i < n; i++) { for (let j = i + 1; j < n; j++) { if (temperatures[j] > temperatures[i]) { answer[i] = j - i; // first warmer day found: stop looking break; } } } return answer;}Brute force: look forward from every day
function dailyTemperatures(temperatures) { const n = temperatures.length; const answer = new Array(n).fill(0); for (let i = 0; i < n; i++) { for (let j = i + 1; j < n; j++) { if (temperatures[j] > temperatures[i]) { answer[i] = j - i; // first warmer day found: stop looking break; } } } return answer;}def daily_temperatures(temperatures): n = len(temperatures) answer = [0] * n for i in range(n): for j in range(i + 1, n): if temperatures[j] > temperatures[i]: answer[i] = j - i # first warmer day found: stop looking break return answernew Array(n).fill(0) (JavaScript) and [0] * n (Python) both make a list of
n zeros, so any day we never fill keeps the answer 0.
On a list that only gets colder, like [30, 29, 28, …], no day ever finds a
warmer one, so every day walks all the way to the end. With 5 days that’s
4 + 3 + 2 + 1 = 10 looks. With 100,000 days it’s about
100,000 × 100,000 ÷ 2 = 5,000,000,000 looks. That’s
O(n²): double the days, four times the work.
A monotonic stack is a stack whose values always go in one direction from bottom to top: always getting smaller (decreasing) or always getting bigger (increasing). “Monotonic” just means “moving one way only”. We keep it that way by popping items before pushing a new one that would break the order.
Pattern
Monotonic stack (next greater element)
Use it when: for each item you need the NEXT (or previous) item that is bigger or smaller than it.
Signal words
- “next greater”
- “next warmer”
- “how many days until”
- “next larger element”
- “stock span”
We store indexes (day numbers) on the stack, not temperatures. From an
index we can always look up the temperature, and we need the index to work out
the distance i − j.
- Make
answer, a list of zeros, and an emptystackof day indexes. - Walk through the days. Call today’s index
i. - While the stack isn’t empty and today is warmer than the day on top: pop that day
jand writeanswer[j] = i − j. - Push today’s index
i. It now waits for its own warmer day. - When the loop ends, every day still on the stack never found a warmer day; their answer stays 0.
Press Play. Bars waiting on the stack are shaded; when a warm day arrives,
watch it knock out the colder bars one by one, and the answers appear above
them (and in the answer row). Then try the edge cases: when it only gets
colder, nothing is ever popped; with equal days, 70° does not pop 70°.
Monotonic stack of waiting days
temperatures = [73, 71, 69, 72, 76]
- empty
- 00
- 01
- 02
- 03
- 04
- Today (i)
- Waiting on the stack
- Top of stack, being compared
- Answer just written
- Answer known
Every answer starts at 0 ("no warmer day"). The stack will hold the days that are still waiting for a warmer day. Their temperatures go DOWN (or stay equal) from bottom to top.
Which line is running?
function dailyTemperatures(temperatures) { const answer = new Array(temperatures.length).fill(0);Running now: const stack = []; // indexes of days still waiting for a warmer day for (let i = 0; i < temperatures.length; i++) { // today is warmer than the day on top: that day's wait is over while (stack.length > 0 && temperatures[i] > temperatures[stack.at(-1)]) { const j = stack.pop(); answer[j] = i - j; } stack.push(i); // today waits for its own warmer day } return answer;}Monotonic stack
function dailyTemperatures(temperatures) { const answer = new Array(temperatures.length).fill(0); const stack = []; // indexes of days still waiting for a warmer day for (let i = 0; i < temperatures.length; i++) { // today is warmer than the day on top: that day's wait is over while (stack.length > 0 && temperatures[i] > temperatures[stack.at(-1)]) { const j = stack.pop(); answer[j] = i - j; } stack.push(i); // today waits for its own warmer day } return answer;}def daily_temperatures(temperatures): answer = [0] * len(temperatures) stack = [] # indexes of days still waiting for a warmer day for i, temp in enumerate(temperatures): # today is warmer than the day on top: that day's wait is over while stack and temp > temperatures[stack[-1]]: j = stack.pop() answer[j] = i - j stack.append(i) # today waits for its own warmer day return answerThe two versions line up line for line until line 9, where JavaScript has a
closing }; after that, JavaScript is one line ahead.
- Line 1: define the function. (LeetCode wraps it as
var dailyTemperatures = function(temperatures)in JavaScript, or a method ofclass Solutionin Python.) - Line 2: a list of zeros, one per day. Zero is the right answer for any day that never gets popped.
- Line 3: the stack of indexes of days still waiting.
- Line 4: walk through the days. Python’s
enumerategives us both the indexiand the temperaturetemp. - Line 6: the heart of the pattern.
stack.at(-1)/stack[-1]is the index on top. We keep popping while today is warmer, because one warm day can end the wait of several colder days at once. Thestack.length > 0/stack andpart comes first so we never look at the top of an empty stack. - Line 7: pop the waiting day
j. - Line 8: its answer is the distance from
jto today. - Line 10 (JS) / line 9 (Py): push today. It goes on top of days that are all at least as warm, so the stack stays decreasing.
- Line 12 (JS) / line 10 (Py): return the answers.
Trace temperatures = [73, 71, 69, 72, 76]. The stack shows indexes with their
temperatures, bottom → top.
| i | temp | pops (j: answer[j] = i − j) | stack after | answer after |
|---|---|---|---|---|
| 0 | 73° | — | [0:73] | [0, 0, 0, 0, 0] |
| 1 | 71° | — (71 is not > 73) | [0:73, 1:71] | [0, 0, 0, 0, 0] |
| 2 | 69° | — (69 is not > 71) | [0:73, 1:71, 2:69] | [0, 0, 0, 0, 0] |
| 3 | 72° | 2: 1, then 1: 2 (stop at 73) | [0:73, 3:72] | [0, 2, 1, 0, 0] |
| 4 | 76° | 3: 1, then 0: 4 | [4:76] | [4, 2, 1, 1, 0] |
The 72° row (i = 3) shows the payoff: one warm day (72°) answers two waiting days at once, and it stops at 73° without looking any further down.
Brute force
Time
O(n²)
Each day may walk to the end of the list: about n × n ÷ 2 looks.
Space
O(1) extra
Only two indexes, besides the answer list we must return anyway.
Monotonic stack
Time
O(n)
Each day is pushed exactly once and popped at most once, so all the while-loop pops add up to at most n, even though the loop is nested.
Space
O(n)
If temperatures only fall, every day waits on the stack at the same time.
The nested while loop looks like O(n²), but it isn’t. Count pushes and
pops instead of loop turns: each day is pushed once and popped at most once,
so the total work is at most 2n steps. This “count what happens to each item”
trick is called amortized analysis.
What to say out loud, in this order:
- Restate: “for each day, the distance to the next strictly warmer day, or 0.”
- Brute force: “scan forward from each day, O(n²) on a falling list.”
- Key insight: “the days still waiting always have decreasing temperatures, and a new day settles the most recent ones first, so a monotonic stack of indexes.”
- Explain why it’s O(n) even with the nested loop: each index is pushed and popped at most once.
- Dry-run a day that pops two waiting days at once.
Likely follow-up questions:
- “Next smaller element instead?” Flip the comparison: keep an increasing stack.
- “Previous greater element?” Same stack; read the top after popping, before pushing.
- “Can you do it with O(1) extra space?” Yes: walk from the right and use the answers already computed to jump ahead. A nice follow-up to mention, not required.
Related problems:
- Car Fleet (this week): another stack that only keeps items that “still matter”, after sorting.
- Largest Rectangle in Histogram (LeetCode 84, a good extra challenge): the hardest monotonic-stack classic.
- The week 3 overview has the reusable template.