Part 10 · Lesson 40 · read
Monotonic Stack
Find the next bigger item. It also solves temperatures, stock spans, histograms and rain water.
On this page
The question: next greater element
The next greater element of an item is the first item to its right that is bigger than it. For every item in an array, find it. If there is none, the answer is -1. For [2, 1, 5, 3, 4] the answers are [5, 5, -1, 4, -1]. The simple way is to scan to the right from every item:
// For each item, scan right until something bigger appears.function nextGreaterBrute(nums) { const out = new Array(nums.length).fill(-1); for (let i = 0; i < nums.length; i++) { for (let j = i + 1; j < nums.length; j++) { if (nums[j] > nums[i]) { out[i] = nums[j]; break; } } } return out;}console.log(nextGreaterBrute([2, 1, 5, 3, 4])); // [5, 5, -1, 4, -1] O(n²) in the worst case (a descending array)If the array goes down (descending), every scan runs to the end. So this is O(n²), which is slow for big arrays. Questions like this ("the next warmer day", "how many days was the price below today", "the nearest taller building") come up again and again. One structure solves them all in O(n).
The idea: a stack of unanswered items
Walk from left to right. Keep a stack of the items that are still waiting for their answer. When a new value arrives, it is the answer for every waiting item that is smaller than it. So pop those items and record the answer. Then push the new value, because it now waits for its own answer. The values in the stack never go up from bottom to top, because every smaller value is popped when a bigger one arrives. A stack that stays in order like this is called a monotonic stack (monotonic means always going the same way).
function nextGreater(nums) { const out = new Array(nums.length).fill(-1); const stack = []; // indices still waiting for a greater value; their values never increase for (let i = 0; i < nums.length; i++) { while (stack.length && nums[stack[stack.length - 1]] < nums[i]) { out[stack.pop()] = nums[i]; // nums[i] is the answer for everything it is bigger than } stack.push(i); } return out; // what is left on the stack keeps its -1}console.log(nextGreater([2, 1, 5, 3, 4])); // [5, 5, -1, 4, -1]console.log(nextGreater([4, 3, 2, 1])); // [-1, -1, -1, -1]Why is it O(n)? Each index is pushed once and popped at most once. So the inner while loop does not multiply the work of the outer loop. Across the whole run, it runs at most n times in total.
Traced: daily temperatures
Daily Temperatures: for each day, how many days until a warmer day? It is the same pattern. But the answer is the distance between two positions, so the stack stores indices (positions) instead of values.
The stack holds the days that are still waiting for a warmer day. Their temperatures never go up from bottom to top. That is what monotonic means: always going the same way.
▶const answer = new Array(n).fill(0);2const stack = [];3for (let i = 0; i < n; i++) {4 while (stack.length && temps[stack[stack.length - 1]] < temps[i]) {5 const j = stack.pop();6 answer[j] = i - j;7 }8 stack.push(i);9}| answer | [0, 0, 0, 0, 0, 0, 0, 0] |
| stack | [] |
The template and its variations
| Wanted | Rule | Note |
|---|---|---|
| next greater to the right | pop while the stack top < current | the current item is the answer for each item you pop |
| next smaller to the right | pop while the stack top > current | same idea, with the comparison the other way round |
| previous greater / smaller to the left | the popped items are not the answer. Read the stack top before you push | after popping, the top is the nearest bigger (or smaller) value on the left |
| equal values | choose < or <= on purpose | decides whether an equal value counts as 'greater' |
Store indices when you need distances or widths. Store values when you only need the value. Storing indices works in both cases.
< or <= decides what happens with equal values. For "next strictly greater" (it must be bigger, not equal), pop while <. If an equal value should count as the answer, use <=. Test with an array like [2, 2] before you submit.Circular arrays
Sometimes the array wraps around: after the last item, you look at the first item again. In this case, loop through the indices twice using i % n (the remainder after dividing i by n, which sends the index back to the start). Push only during the first lap. The second lap lets every item see the items that come before it.
// Next greater element, treating the array as a circle.function nextGreaterCircular(nums) { const n = nums.length; const out = new Array(n).fill(-1); const stack = []; for (let i = 0; i < 2 * n; i++) { // go around twice const x = nums[i % n]; while (stack.length && nums[stack[stack.length - 1]] < x) { out[stack.pop()] = x; } if (i < n) stack.push(i); // only push during the first lap } return out;}console.log(nextGreaterCircular([1, 2, 1])); // [2, -1, 2]console.log(nextGreaterCircular([5, 4, 3, 2, 1])); // [-1, 5, 5, 5, 5]Stock span: looking backwards
The span of today's price is the number of days in a row, ending today, with a price that is today's price or lower. The stack holds [price, span] pairs. A new price takes in every pair on top of the stack that has a smaller or equal price. It adds their spans to its own. So no day is ever counted twice.
class StockSpanner { constructor() { this.stack = []; } // [price, span] pairs, prices strictly decreasing next(price) { let span = 1; while (this.stack.length && this.stack[this.stack.length - 1][0] <= price) { span += this.stack.pop()[1]; // absorb the span of every smaller-or-equal day } this.stack.push([price, span]); return span; }}const s = new StockSpanner();console.log([100, 80, 60, 70, 60, 75, 85].map((p) => s.next(p))); // [1, 1, 1, 2, 1, 4, 6]Largest rectangle in a histogram
A histogram is a bar chart: bars of different heights, all of width 1, standing side by side. You get the heights of the bars. Find the largest rectangle that fits inside the bars. For each bar, the widest rectangle that uses its full height goes left and right until it meets a shorter bar. Those edges are exactly the previous smaller and next smaller elements. A monotonic stack of increasing heights finds them in one pass. When a shorter bar arrives at index i, each taller bar on the stack is finished. Its right edge is i. Its left edge is the bar that is now under it on the stack.
function largestRectangle(heights) { const stack = []; // indices of bars with increasing heights let best = 0; for (let i = 0; i <= heights.length; i++) { const h = i === heights.length ? 0 : heights[i]; // a bar of height 0 at the end flushes the stack while (stack.length && heights[stack[stack.length - 1]] > h) { const height = heights[stack.pop()]; const left = stack.length ? stack[stack.length - 1] : -1; // the first smaller bar on the left best = Math.max(best, height * (i - left - 1)); // i is the first smaller bar on the right } stack.push(i); } return best;}console.log(largestRectangle([2, 1, 5, 6, 2, 3])); // 10 (heights 5 and 6, width 2)console.log(largestRectangle([2, 4])); // 4console.log(largestRectangle([1, 1, 1, 1])); // 4| Event | Stack (heights) | Rectangle found |
|---|---|---|
| i=0, h=2: push | 2 | - |
| i=1, h=1: pop 2 (left = -1) | 1 | 2 × (1 − (−1) − 1) = 2 |
| i=2, h=5: push | 1, 5 | - |
| i=3, h=6: push | 1, 5, 6 | - |
| i=4, h=2: pop 6 (left = 2) | 1, 5 | 6 × (4 − 2 − 1) = 6 |
| i=4: pop 5 (left = 1) | 1 | 5 × (4 − 1 − 1) = 10 |
| i=4: push | 1, 2 | - |
| i=5, h=3: push | 1, 2, 3 | - |
| i=6 (sentinel 0): pop 3, 2, 1 | empty | 3×1=3, 2×4=8, 1×6=6 |
The best rectangle is 10. It is made by the bars of height 5 and 6 side by side. The sentinel is a fake extra bar of height 0 added at the end. It forces every bar still on the stack to be finished.
Trapping rain water
Water sits above a bar. It rises up to the lower of the two tallest bars, one on each side. A monotonic stack finds each "pool" as soon as its right wall appears. Pop the floor. The new top of the stack is the left wall. The pool holds width × (lower wall − floor) water.
function trapStack(height) { const stack = []; // indices of bars, heights decreasing let water = 0; for (let i = 0; i < height.length; i++) { while (stack.length && height[stack[stack.length - 1]] < height[i]) { const bottom = stack.pop(); // the floor of a pool if (!stack.length) break; // no left wall const left = stack[stack.length - 1]; const width = i - left - 1; const depth = Math.min(height[left], height[i]) - height[bottom]; water += width * depth; } stack.push(i); } return water;}console.log(trapStack([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])); // 6console.log(trapStack([4, 2, 0, 3, 2, 5])); // 9There is also a smarter version with two pointers. It needs only O(1) space (a fixed amount of extra memory, however long the input is). The shorter side always decides the water level at its own position, because the other side has a wall at least as tall:
function trap(height) { let l = 0, r = height.length - 1; let leftMax = 0, rightMax = 0, water = 0; while (l < r) { if (height[l] < height[r]) { // the shorter side decides: its water level is limited by its own max leftMax = Math.max(leftMax, height[l]); water += leftMax - height[l]; l++; } else { rightMax = Math.max(rightMax, height[r]); water += rightMax - height[r]; r--; } } return water;}console.log(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])); // 6console.log(trap([4, 2, 0, 3, 2, 5])); // 9The best answer is to know both. The stack version shows the pattern. The two-pointer version shows that you can save memory once you understand why it works.
Practice questions
Ask yourself: "What is each item waiting for?" The answer is the condition that pops the stack.
For each number in nums1, find the first bigger number to its right in nums2. If there is none, the answer is −1. All numbers are different.
Hint 1
Hint 2
Show all 2 solutions with explanations
For each value of nums1, find it in nums2 and scan to the right.
function nextGreaterElement(nums1, nums2) { return nums1.map((x) => { const start = nums2.indexOf(x); for (let j = start + 1; j < nums2.length; j++) if (nums2[j] > x) return nums2[j]; return -1; });}console.log(nextGreaterElement([4, 1, 2], [1, 3, 4, 2])); // [-1, 3, -1]O(m·n), where m is the length of nums1 and n is the length of nums2.
Go through nums2 once with the stack. Whenever you pop a value, its answer is the current value. Then look up each nums1 value in the Map.
function nextGreaterElement(nums1, nums2) { const next = new Map(); const stack = []; for (const x of nums2) { while (stack.length && stack[stack.length - 1] < x) next.set(stack.pop(), x); stack.push(x); } return nums1.map((x) => next.get(x) ?? -1);}console.log(nextGreaterElement([4, 1, 2], [1, 3, 4, 2])); // [-1, 3, -1]console.log(nextGreaterElement([2, 4], [1, 2, 3, 4])); // [3, -1]O(m + n). You can store values (not indices) because all the values in nums2 are different.
Use the stack with a Map. (LeetCode 496.)
The same question, but the array is circular. The search for the next greater value may wrap around to the start.
Hint 1
Show all 2 solutions with explanations
For every index, check the next n − 1 positions. Use modulo (%, the remainder) to wrap back to the start.
function nextGreaterElements(nums) { const n = nums.length; return nums.map((x, i) => { for (let step = 1; step < n; step++) { const y = nums[(i + step) % n]; if (y > x) return y; } return -1; });}console.log(nextGreaterElements([1, 2, 1])); // [2, -1, 2]O(n²).
Loop i from 0 to 2n − 1 and read nums[i % n]. Push indices only during the first lap.
function nextGreaterElements(nums) { const n = nums.length; const out = new Array(n).fill(-1); const stack = []; for (let i = 0; i < 2 * n; i++) { const x = nums[i % n]; while (stack.length && nums[stack[stack.length - 1]] < x) out[stack.pop()] = x; if (i < n) stack.push(i); } return out;}console.log(nextGreaterElements([1, 2, 1])); // [2, -1, 2]console.log(nextGreaterElements([1, 2, 3, 4, 3])); // [2, 3, 4, -1, 4]O(n). There are at most n pushes and n pops in total. Two laps are enough, because any answer is within n − 1 steps.
Use the stack. (LeetCode 503.)
For each day, return how many days you must wait for a warmer temperature. If it never gets warmer, return 0.
Hint 1
Show all 3 solutions with explanations
For each day, look ahead until you find a warmer day.
function dailyTemperatures(temps) { return temps.map((t, i) => { for (let j = i + 1; j < temps.length; j++) if (temps[j] > t) return j - i; return 0; });}console.log(dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73])); // [1, 1, 4, 2, 1, 1, 0, 0]O(n²) when the temperatures keep going down.
Pop every waiting day that is colder than today. Its answer is i − j.
function dailyTemperatures(temps) { const answer = new Array(temps.length).fill(0); const stack = []; for (let i = 0; i < temps.length; i++) { while (stack.length && temps[stack[stack.length - 1]] < temps[i]) { const j = stack.pop(); answer[j] = i - j; } stack.push(i); } return answer;}console.log(dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73])); // [1, 1, 4, 2, 1, 1, 0, 0]console.log(dailyTemperatures([30, 40, 50, 60])); // [1, 1, 1, 0]O(n) time and space.
Walk backwards and use the answers you already have to jump ahead. If temps[j] is not warmer, jump to the day j + answer[j], which was warmer than day j.
function dailyTemperatures(temps) { const n = temps.length; const answer = new Array(n).fill(0); for (let i = n - 2; i >= 0; i--) { let j = i + 1; while (j < n && temps[j] <= temps[i]) { if (answer[j] === 0) { j = n; break; } // nothing warmer than temps[j] exists, so nothing warmer than temps[i] either j += answer[j]; } answer[i] = j < n ? j - i : 0; } return answer;}console.log(dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73])); // [1, 1, 4, 2, 1, 1, 0, 0]O(n) without a stack, but it is harder to prove that it works. It is good to know it exists. In an interview, use the stack.
Use the stack. (LeetCode 739.)
Each call next(price) returns the number of days in a row, up to and including today, with a price ≤ today's price.
Hint 1
Hint 2
Show all 2 solutions with explanations
Keep every price. For each new price, count backwards while the earlier prices are at most today's price.
class StockSpanner { constructor() { this.prices = []; } next(price) { this.prices.push(price); let span = 0; for (let i = this.prices.length - 1; i >= 0 && this.prices[i] <= price; i--) span++; return span; }}const s = new StockSpanner();console.log([100, 80, 60, 70, 60, 75, 85].map((p) => s.next(p))); // [1, 1, 1, 2, 1, 4, 6]O(n) per call. If the prices keep going up, the total is O(n²).
Pop all entries with a price ≤ today's price, and add their spans to today's span. Then push the result.
class StockSpanner { constructor() { this.stack = []; } next(price) { let span = 1; while (this.stack.length && this.stack[this.stack.length - 1][0] <= price) { span += this.stack.pop()[1]; } this.stack.push([price, span]); return span; }}const s = new StockSpanner();console.log([100, 80, 60, 70, 60, 75, 85].map((p) => s.next(p))); // [1, 1, 1, 2, 1, 4, 6]The average cost is O(1) per call (amortised), because each entry is pushed once and popped at most once.
Use the stack with spans. (LeetCode 901.)
You get the bar heights (each bar has width 1). Return the area of the largest rectangle that fits inside the histogram.
Hint 1
Hint 2
Show all 2 solutions with explanations
For each bar, walk left and right as long as the bars are at least as tall. The area is height × width.
function largestRectangle(heights) { let best = 0; for (let i = 0; i < heights.length; i++) { let l = i, r = i; while (l > 0 && heights[l - 1] >= heights[i]) l--; while (r < heights.length - 1 && heights[r + 1] >= heights[i]) r++; best = Math.max(best, heights[i] * (r - l + 1)); } return best;}console.log(largestRectangle([2, 1, 5, 6, 2, 3])); // 10O(n²).
When a shorter bar arrives, pop the taller bars. Each popped bar's rectangle spans from the new stack top to the current index. Add a bar of height 0 at the end to empty the stack.
function largestRectangle(heights) { const stack = []; let best = 0; for (let i = 0; i <= heights.length; i++) { const h = i === heights.length ? 0 : heights[i]; while (stack.length && heights[stack[stack.length - 1]] > h) { const height = heights[stack.pop()]; const left = stack.length ? stack[stack.length - 1] : -1; best = Math.max(best, height * (i - left - 1)); } stack.push(i); } return best;}console.log(largestRectangle([2, 1, 5, 6, 2, 3])); // 10console.log(largestRectangle([2, 4])); // 4console.log(largestRectangle([1, 1, 1, 1])); // 4O(n). When two bars have equal heights, the later bar is popped first, and its width stops at the earlier equal bar. But the earlier bar is popped afterwards, and its rectangle covers the full width. So the biggest area is still correct.
Use the stack. This is one of the hard questions that interviewers ask most. Practise until you can write it without looking. (LeetCode 84.)
You get the heights of bars that are each 1 wide. Work out how much rain water is trapped between them.
Hint 1
min(tallest bar to its left, tallest bar to its right) − its own height.Hint 2
Show all 3 solutions with explanations
The arrays leftMax[i] and rightMax[i] give the two walls for every bar. Add up min(...) − height for all bars.
function trap(height) { const n = height.length; const leftMax = new Array(n), rightMax = new Array(n); let m = 0; for (let i = 0; i < n; i++) { m = Math.max(m, height[i]); leftMax[i] = m; } m = 0; for (let i = n - 1; i >= 0; i--) { m = Math.max(m, height[i]); rightMax[i] = m; } let water = 0; for (let i = 0; i < n; i++) water += Math.min(leftMax[i], rightMax[i]) - height[i]; return water;}console.log(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])); // 6console.log(trap([4, 2, 0, 3, 2, 5])); // 9O(n) time, O(n) space. It is the same idea as a prefix sum (a running total), but it keeps the biggest value so far instead of the sum.
Keep the indices of bars whose heights go down. When a taller bar arrives, pop the floor bar. Then fill the pool between the new top bar and the current bar.
function trap(height) { const stack = []; let water = 0; for (let i = 0; i < height.length; i++) { while (stack.length && height[stack[stack.length - 1]] < height[i]) { const bottom = stack.pop(); if (!stack.length) break; const left = stack[stack.length - 1]; water += (i - left - 1) * (Math.min(height[left], height[i]) - height[bottom]); } stack.push(i); } return water;}console.log(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])); // 6console.log(trap([4, 2, 0, 3, 2, 5])); // 9O(n) time, O(n) space. This version counts the water in horizontal layers, not bar by bar.
Move in from the shorter side. The water level there is set by the tallest bar seen so far on that side, because the other side has a wall that is equal or taller.
function trap(height) { let l = 0, r = height.length - 1, leftMax = 0, rightMax = 0, water = 0; while (l < r) { if (height[l] < height[r]) { leftMax = Math.max(leftMax, height[l]); water += leftMax - height[l++]; } else { rightMax = Math.max(rightMax, height[r]); water += rightMax - height[r--]; } } return water;}console.log(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])); // 6console.log(trap([4, 2, 0, 3, 2, 5])); // 9O(n) time and O(1) space. This is the best final answer. Show the left-and-right-maximum version first, because it is easy to explain.
Take the interviewer step by step: first the left and right maximum arrays, then two pointers. (LeetCode 42.)
Remove exactly k digits from a number string. The number that is left must be as small as possible.
Hint 1
Hint 2
Show all 2 solutions with explanations
Try deleting each digit, and repeat this k times. Each time, keep the smaller result.
function removeKdigits(num, k) { while (k > 0 && num.length > 0) { let best = null; for (let i = 0; i < num.length; i++) { const cand = num.slice(0, i) + num.slice(i + 1); if (best === null || BigInt(cand || "0") < BigInt(best || "0")) best = cand; } num = best; k--; } num = num.replace(/^0+/, ""); return num === "" ? "0" : num;}console.log(removeKdigits("1432219", 3)); // 1219console.log(removeKdigits("10200", 1)); // 200Far too slow for long inputs (up to 10⁵ digits). But it makes the goal clear.
- For each digit: while
k > 0and the stack top is bigger than the digit, pop the top. That is one removal. - Push the digit.
- If you still have removals left, remove digits from the end. The stack never goes down, so its end holds the biggest digits.
- Remove the zeros at the front. If nothing is left, return "0".
function removeKdigits(num, k) { const stack = []; for (const d of num) { while (k > 0 && stack.length && stack[stack.length - 1] > d) { stack.pop(); k--; } stack.push(d); } while (k > 0) { stack.pop(); k--; } const result = stack.join("").replace(/^0+/, ""); return result === "" ? "0" : result;}console.log(removeKdigits("1432219", 3)); // 1219console.log(removeKdigits("10200", 1)); // 200console.log(removeKdigits("10", 2)); // 0O(n). You can compare the digit characters directly, because "0" < "9" in text order, just like in number order.
Use the stack. This is another "remove the earlier, bigger item" problem in disguise. (LeetCode 402.)
Make it stick
- Explain what is in the stack at any moment. Explain why it is called monotonic.
- Explain why the loop inside a loop is still O(n).
- Say when to store indices instead of values.
- Explain how each histogram bar finds its left and right edges.
Revisit schedule: solve two of the questions again tomorrow, again in 3 days, and once more in a week — without looking at the answers. Each time it will feel easier. That is the memory forming.
What's next
That completes the linear structures (the ones where items sit in a line): arrays, strings, hash maps, linked lists, stacks and queues. Lesson 41 begins the next part with the first structure that is not a line: binary trees. In a binary tree, a node has up to two children.
Practise on LeetCode
Real interview problems that use exactly what this lesson teaches. Solve them in JavaScript after the practice questions above.
Published by Jainik · Last updated · How these lessons are made
Keep learning
Part of the study guide
Related series