Daily Temperatures: The Monotonic Stack Pattern in One Problem
Solve Daily Temperatures with a monotonic stack in O(n) — right-to-left intuition, worked walkthrough, JavaScript code, complexity, and common mistakes.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Daily Temperatures looks like weather trivia and is actually the cleanest introduction to a quietly powerful interview tool: the monotonic stack. For every day, find how far away the next strictly warmer day is — the obvious solution rescans the future over and over; the stack answers all n queries in one pass.
The trick is a reframe: sweep from the right, keeping a stack of future days still useful as "next warmer day" candidates. Anything that can never be an answer again is discarded exactly once — that discipline collapses O(n²) into O(n), and it unlocks a whole family of problems — next greater element, stock spans, histogram rectangles — that all reduce to one question: which nearby element beats me?
The problem
Given an array arr of daily temperatures, return an array ans where ans[i] is the number of days you have to wait after day i for a strictly warmer temperature. If no warmer day ever comes, ans[i] stays 0.
Input: arr = [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1, 1, 4, 2, 1, 1, 0, 0]
Day 2 (75) waits 4 days for 76. Day 6 (76) never sees warmer → 0.Two details shape the solution:
- The answer is a distance in days, not a temperature — your bookkeeping must remember positions, not just values.
- "Warmer" means strictly greater. A future day with an equal temperature does not count.
The brute force baseline
For each day, scan forward until you find something warmer:
function dailyTemperatures(arr) {
const n = arr.length;
const ans = Array(n).fill(0);
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
if (arr[j] > arr[i]) {
ans[i] = j - i;
break;
}
}
}
return ans;
}Correct, and O(n²) in the worst case. On a strictly decreasing input like [80, 75, 70, 65, 60] no day ever finds warmth, so every inner loop runs to the end — roughly n²/2 comparisons, about five billion steps at LeetCode's 10⁵ limit. The waste is obvious once you name it: day 3 rescans the same future day 2 just walked through, learning nothing from its work.
The key insight: keep only the useful future
This is the monotonic stack pattern. Sweep from right to left, maintaining a stack of indices of future days that could still be someone's next warmer day.
The core observation is redundancy. Standing at day i, if a future day top on the stack has arr[top] <= arr[i], it is dead weight: any day to the left of i looking for warmth hits day i first, and day i is at least as warm. top can never be anyone's answer again — pop it, permanently.
Popping everything day i dominates leaves the stack with a strict shape: temperatures increase from top to bottom, indices get nearer toward the top. That makes the lookup free — the top is at once the nearest future day and the coolest surviving candidate:
- If the top is strictly warmer than day
i, it is the next warmer day. Answer:top - i. - If the stack empties first, nothing in the future beats day
i. Answer stays0.
Either way, day i then pushes itself as a candidate for the days to its left. Pushed once, popped at most once — that pair of facts is the entire complexity proof.
The optimal solution
This is exactly the algorithm the interactive visualizer steps through line by line:
var dailyTemperatures = function(arr) {
let stack = [];
let n = arr.length;
let ans = Array(n).fill(0);
stack.push(n - 1); // seed last index
for (let i = n - 2; i >= 0; i--) {
while (stack.length) {
let top = stack[stack.length - 1];
if (arr[i] >= arr[top]) {
stack.pop();
} else {
ans[i] = top - i;
break;
}
}
stack.push(i);
}
return ans;
};Four lines carry all the weight:
stack.push(n - 1)— the last day has no future: its answer is locked at 0 and it becomes everyone's first candidate.arr[i] >= arr[top]— the pop uses>=, not>. An equal-temperature day is not warmer, so it must be evicted too, or it would masquerade as an answer.ans[i] = top - i; break— the first strictly warmer top is the nearest one, because closer days sit above farther ones. Stop immediately; deeper entries are only warmer-but-farther.stack.push(i)— unconditional, even when the stack emptied andans[i]stayed 0. Dayimay still answer a cooler day to its left.
Walkthrough: arr = [73, 74, 71, 76]
| Step | i | arr[i] | Stack before (bottom → top) | Comparison | Action | ans |
|---|---|---|---|---|---|---|
| 1 | — | — | [] | — | seed: push 3 | [0, 0, 0, 0] |
| 2 | 2 | 71 | [3] | 71 ≥ 76? no | ans[2] = 3−2 = 1, push 2 | [0, 0, 1, 0] |
| 3 | 1 | 74 | [3, 2] | 74 ≥ 71? yes | pop index 2 | [0, 0, 1, 0] |
| 4 | 1 | 74 | [3] | 74 ≥ 76? no | ans[1] = 3−1 = 2, push 1 | [0, 2, 1, 0] |
| 5 | 0 | 73 | [3, 1] | 73 ≥ 74? no | ans[0] = 1−0 = 1, push 0 | [1, 2, 1, 0] |
| 6 | — | — | [3, 1, 0] | — | return | [1, 2, 1, 0] |
Step 3 is the pattern in miniature. Day 1 (74°) beats day 2 (71°), so day 2 can never again be anyone's next warmer day — anything left of day 1 reaches 74° first. Popped, never touched again. The survivor beneath, day 3 (76°), is strictly warmer and answers day 1 instantly.
Run a strictly decreasing input like [80, 75, 70] and you see the other exit: each day pops everything, hits an empty stack, keeps its 0, and pushes itself — [0, 0, 0] with no special-case code.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Brute force rescan | O(n²) | O(1) | each day may scan the whole future |
| Monotonic stack | O(n) | O(n) | each index pushed once, popped ≤ once |
The nested while inside the for fools people. Count operations by element, not loop level: every index enters the stack once and leaves at most once, so total pop work is bounded by n — about 2n stack operations overall. Space is O(n): a decreasing input keeps every index on the stack.
Common mistakes
- Pushing temperatures instead of indices. The answer is a day gap; temperatures alone can never compute
top - i. Indices give both — compare viaarr[top], subtract for distance. - Using
>instead of>=in the pop condition. With strict>, an equal-temperature day survives on the stack and gets reported as "warmer." The>=is what enforces strictly warmer. - Forgetting the
break. After recording an answer the loop must stop — and since theelsebranch doesn't pop, omittingbreakspins forever on the same top. - Skipping
stack.push(i)when no answer was found. A day ending withans[i] = 0is still a legitimate candidate for cooler days to its left; the push is unconditional. - Reversing the subtraction. Sweeping right to left, the warmer day sits at a larger index: the wait is
top - i, noti - top. - Calling it O(n²) in the interview. "Nested loops, so quadratic" is a red flag; lead with the push-once-pop-once argument instead.
Where this pattern shows up next
Daily Temperatures is the canonical "next greater element" problem in a costume; the stack discipline transfers directly:
- Next Greater Element I — the same question in its purest form, plus a hash map to serve subset queries.
- Next Greater Element II — the circular-array twist: same stack, one lap of extra sweeping.
- Evaluate Reverse Polish Notation — a different stack superpower: evaluation machine instead of candidate filter.
- Remove Outermost Parentheses — stack thinking (tracking depth) even when you optimize the stack away.
You can also step through Daily Temperatures interactively and watch the stack shed dead candidates in real time — the "Always decreasing" test case sends every index riding the stack to the very end.
FAQ
Why is Daily Temperatures O(n) if there is a while loop inside a for loop?
Because loop nesting bounds nothing by itself — total work does. Each of the n indices is pushed exactly once and popped at most once, so the sum of all while-loop iterations across the entire run is at most n, for roughly 2n stack operations total: O(n) amortized. A single day can trigger many pops, but every pop permanently destroys a candidate no later step revisits.
Why does the stack store indices instead of temperatures?
The output is a number of days, not a temperature, so you need positions to compute the gap top - i. Indices give you everything: the temperature is one lookup away (arr[top]) and the distance is a subtraction. Temperatures alone cannot produce the answer; storing both is redundant.
Should I solve Daily Temperatures left to right or right to left?
Both are correct, both are O(n), and both keep temperatures decreasing toward the top of the stack. Left to right pops resolved days: a warmer arrival pops every cooler waiting day and fills in their answers. Right to left — the version taught here and in the visualizer — pops dead candidates: the current day evicts future days it dominates, then reads its answer off the surviving top. Each answer lands exactly when its day is processed, which makes the trace easier to follow.
Why does the pop condition use >= instead of >?
Because the problem asks for a strictly warmer day. When arr[i] equals arr[top], day top is not a valid answer for day i — nor for any cooler day to the left, which reaches the equally warm day i first. If you pop only on strict >, the equal-temperature day survives, the else branch fires, and you record a wait time to a day that is not actually warmer.
What is a monotonic stack, in one sentence?
A stack that maintains a sorted invariant — here, temperatures strictly increasing from top to bottom — by evicting violators before each push, so the top is always the nearest element that can still answer a "next greater / next smaller" query in O(1).
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.