Pattern Reference
Monotonic Stack
"Next greater/smaller element, largest rectangle in histogram, trapping rain water."
Loading...
Deep Dive Tutorial
A monotonic stack keeps elements in either increasing or decreasing order. When a new element violates the monotonic property, you pop elements until it doesn't — and those pops are when you compute answers. Since each element is pushed and popped at most once, the total work is O(n).
lightbulb
Which direction?
- Monotonic decreasing (stack top is largest): use for "next greater element" — pop when current is greater than top
- Monotonic increasing (stack top is smallest): use for "next smaller element" — pop when current is smaller than top
The element that triggers a pop IS the answer for the popped element.
- Monotonic decreasing (stack top is largest): use for "next greater element" — pop when current is greater than top
- Monotonic increasing (stack top is smallest): use for "next smaller element" — pop when current is smaller than top
The element that triggers a pop IS the answer for the popped element.
Next Greater Element template
// For each element, find the next element to the right that is strictly greater.
function nextGreaterElement(nums) {
const result = new Array(nums.length).fill(-1);
const stack = []; // stores indices, not values
for (let i = 0; i < nums.length; i++) {
// Pop all elements smaller than current — current is their "next greater"
while (stack.length && nums[stack.at(-1)] < nums[i]) {
result[stack.pop()] = nums[i];
}
stack.push(i);
}
return result;
// remaining in stack have no next greater → result stays -1
}Sliding Window Maximum (Monotonic Deque) — O(n)
// Maintain a deque of indices in decreasing order of nums[].
// Front of deque = index of max in current window.
function maxSlidingWindow(nums, k) {
const dq = []; // indices, front has current window max
const result = [];
for (let i = 0; i < nums.length; i++) {
// Remove indices out of window
while (dq.length && dq[0] < i - k + 1) dq.shift();
// Remove smaller elements from back (they can never be max while current exists)
while (dq.length && nums[dq.at(-1)] < nums[i]) dq.pop();
dq.push(i);
if (i >= k - 1) result.push(nums[dq[0]]);
}
return result;
}Worked Problems
More Worked Problems
Even More Worked Problems
brain
Monotonic stack direction guide:
- Decreasing stack → pop when GREATER element arrives → finds "next greater element"
- Increasing stack → pop when SMALLER element arrives → finds "next smaller element"
- Process right→left instead → finds "previous greater/smaller"
- Histogram / contribution: use both sides (left[] and right[] boundaries)
- "Minimize/maximize by removing k elements" → greedy with monotonic stack
- "132 pattern / jump patterns" → scan backwards, pop = candidate for middle value
- Decreasing stack → pop when GREATER element arrives → finds "next greater element"
- Increasing stack → pop when SMALLER element arrives → finds "next smaller element"
- Process right→left instead → finds "previous greater/smaller"
- Histogram / contribution: use both sides (left[] and right[] boundaries)
- "Minimize/maximize by removing k elements" → greedy with monotonic stack
- "132 pattern / jump patterns" → scan backwards, pop = candidate for middle value