What a monotonic stack is
You have daily temperatures
[73, 74, 75, 71, 69, 72, 76, 73] and for each day want: how many days until a warmer one? The brute-force move — scan forward from each day until it finds something warmer — is a loop inside a loop, O(n²), and it keeps re-examining the same future days.A monotonic stack is an ordinary stack that you deliberately keep in sorted order (here, temperatures decreasing from bottom to top). You hold the days still waiting for a warmer day. When a new, warmer day arrives, every cooler day sitting on top has just found its answer, so you pop them all at once.
It's a line of people ordered by height where anyone shorter than the newcomer steps out — they've found who they were waiting for. Each day is pushed once and popped once.
In the animation, split your attention two ways: the stack on the side holds the days still waiting, and the answer row fills in the moment a warmer day pops them. Watch how a single warm day can clear several waiting days in one step — that burst of pops is the whole trick.
This section has a step-by-step animation in the interactive lesson.
Quick check
A new, warmer day arrives. The cooler days waiting on top of the stack…
Answer it in the interactive lesson to keep your progress.
How it works, step by step
Given daily temperatures
[73, 74, 75, 71, 69, 72], for each day we want how many days until a warmer one. Rechecking the future for every day is O(n²); instead we keep a stack of days still waiting for a warmer day, so each warmer arrival resolves everyone it beats at once.The steps
- Keep a stack of indices (not the temperatures). Storing indices lets you subtract positions to get the distance.
- Walk the days left to right. For today's index
i: - While the stack's top day is cooler than today, pop it — it just found its warmer day; its answer is
i - poppedIndex. - Push
ionto the stack. - Anything still on the stack at the end never found a warmer day → its answer stays
0.
Trace it on [73, 74, 75, 71, 69, 72]:
- Day 0 (
73): Push index0. Stack:[0] - Day 1 (
74):74 > 73→ Pop0,answer[0] = 1 - 0 = 1. Push1. Stack:[1] - Day 2 (
75):75 > 74→ Pop1,answer[1] = 2 - 1 = 1. Push2. Stack:[2] - Day 3 (
71):71 < 75→ Cooler, just push3. Stack:[2, 3] - Day 4 (
69):69 < 71→ Cooler, just push4. Stack:[2, 3, 4] - Day 5 (
72):72 > 69→ Pop4,answer[4] = 5 - 4 = 1. Next on stack is3(71), and72 > 71→ Pop3,answer[3] = 5 - 3 = 2.72 < 75, so stop popping and push5. Stack:[2, 5]
Each warmer day clears out everyone it beats, in a single pass. In JavaScript, one way to write those steps:
function dailyTemps(t) {
const answer = new Array(t.length).fill(0);
const stack = []; // indices of days awaiting a warmer day
for (let i = 0; i < t.length; i++) {
while (stack.length && t[stack[stack.length - 1]] < t[i]) {
const day = stack.pop();
answer[day] = i - day; // distance in days
}
stack.push(i);
}
return answer;
}
console.log(dailyTemps([73, 74, 75, 71, 69, 72, 76, 73])); // [1,1,4,2,1,1,0,0]Quick check
Stack holds indices [2, 3, 4] (temps 75, 71, 69) and day 5 arrives at 72. Predict the pops.
Answer it in the interactive lesson to keep your progress.
Where it breaks (and how not to get burned)
- Wrong direction of monotonicity. "Next greater" wants a decreasing stack; "next smaller" wants increasing. Pick the direction from what you are searching for, or every answer flips.
- Storing values instead of indices. For distance/position answers you need indices; store those and read the value via the array.
- Leftovers. Elements still on the stack at the end never found their target — assign them the default (e.g.
0or-1), do not forget them.
Quick check
For a *distance* answer (like daily temperatures), the stack must hold…
Answer it in the interactive lesson to keep your progress.
Take it further — next greater element
Change one line and you get another classic: instead of recording the distance, record the value of the warmer day. That's next greater element — for each number, the first bigger number to its right (or
-1 if none). Same stack, same pop rule, different thing stored.In the animation, watch what gets written when a pop happens: not the distance this time, but the value of the newcomer that caused the pop. Everything else — the decreasing stack, the pop-while-beaten rule, the leftovers defaulting to
-1 — is identical to daily temperatures. One pattern, a family of answers.This section has a step-by-step animation in the interactive lesson.
function nextGreater(nums) {
const result = new Array(nums.length).fill(-1);
const stack = [];
for (let i = 0; i < nums.length; i++) {
while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
result[stack.pop()] = nums[i]; // store the VALUE, not the distance
}
stack.push(i);
}
return result;
}
console.log(nextGreater([2, 1, 2, 4, 3])); // [4, 2, 4, -1, -1]Quick check
On [4, 1, 6], predict the next-greater answer for each element.
Answer it in the interactive lesson to keep your progress.
How fast is it? (complexity)
Using the vocabulary from the Complexity & Time lesson, the inner
while loop looks like it could make this quadratic, but it can't: across the entire run, every index is pushed once and popped at most once, so total pushes + pops ≤ 2n:| Approach to "next warmer day" | Time | Space | Why |
|---|---|---|---|
| re-scan forward from each day | O(n²) | O(1) | re-examines the same future days |
| monotonic stack | O(n) | O(n) | each day pushed once, popped once |
That push-once/pop-once accounting is called an amortized bound — the pops are uneven per step, but bounded in total.
Key takeaways:
- A monotonic stack stays sorted; a newcomer pops everything it beats, resolving many waiting items at once.
- Store indices (read values via the array) so you can compute distances.
- Amortized
O(n): each element enters and leaves the stack once.
The same stack, storing something different, answers a whole family. These classics each get their own lesson later (no need to know them yet): daily temperatures and next greater element (both above), largest rectangle in a histogram (a monotonic stack of bar heights), and trapping rain water / stock span. Next up in order: Linked Lists — values that are not packed side by side; each node points to the next.