Monotonic Stack & Queue
A monotonic stack is a stack whose elements are always in sorted order (either always increasing or always decreasing). When a new element breaks the ordering, you pop until the invariant is restored. Each element is pushed and popped at most once, so the overall complexity stays O(n) even though there is a loop inside the main loop.
This structure solves a whole family of "nearest greater/smaller" problems that naive O(n²) brute force struggles with.
Monotonic Increasing vs Decreasing
Type | Stack order (bottom → top) | Use it to find |
|---|---|---|
Increasing | Smallest at bottom, largest at top | Previous smaller element, next smaller element |
Decreasing | Largest at bottom, smallest at top | Previous greater element, next greater element |
Next Greater Element — Core Pattern
For each element, find the first element to its right that is strictly greater. If none exists, the answer is −1.
// LeetCode 496 — Next Greater Element I
function nextGreaterElement(nums) {
const result = new Array(nums.length).fill(-1);
const stack = []; // stores indices; maintained as monotonically decreasing
for (let i = 0; i < nums.length; i++) {
// Pop all elements smaller than nums[i] — nums[i] is their next greater
while (stack.length > 0 && nums[stack.at(-1)] < nums[i]) {
const idx = stack.pop();
result[idx] = nums[i];
}
stack.push(i);
}
// Remaining elements in stack have no next greater → result stays -1
return result;
}
console.log(nextGreaterElement([2,1,2,4,3])); // [4,2,4,-1,-1]
console.log(nextGreaterElement([1,3,2,4])); // [3,4,4,-1]Previous Smaller Element
For each element, find the nearest element to its left that is strictly smaller. Scan left to right and pop elements ≥ current; whatever remains on top is the answer.
function previousSmallerElement(nums) {
const result = new Array(nums.length).fill(-1);
const stack = []; // monotonically increasing (values, not indices)
for (let i = 0; i < nums.length; i++) {
// Pop elements that are >= nums[i] (they are not "smaller")
while (stack.length > 0 && stack.at(-1) >= nums[i]) {
stack.pop();
}
result[i] = stack.length > 0 ? stack.at(-1) : -1;
stack.push(nums[i]);
}
return result;
}
console.log(previousSmallerElement([4,5,2,10,8])); // [-1,4,-1,2,2]Problem 1 — Daily Temperatures
LeetCode 739. For each day, find how many days until a warmer temperature. This is "next greater element" with the answer expressed as a distance.
function dailyTemperatures(temperatures) {
const n = temperatures.length;
const result = new Array(n).fill(0);
const stack = []; // indices of days waiting for a warmer day
for (let i = 0; i < n; i++) {
while (stack.length > 0 && temperatures[stack.at(-1)] < temperatures[i]) {
const idx = stack.pop();
result[idx] = i - idx; // days to wait
}
stack.push(i);
}
return result;
}
console.log(dailyTemperatures([73,74,75,71,69,72,76,73]));
// [1,1,4,2,1,1,0,0]Problem 2 — Trapping Rain Water
LeetCode 42. Given an elevation map, compute how much water can be trapped.
The monotonic stack approach processes bars one at a time. When a bar taller than the stack top is found, water can be trapped between the popped bar, the new bar, and the bar now on top of the stack (the left boundary).
function trap(height) {
const stack = []; // indices, maintained as decreasing heights
let water = 0;
for (let i = 0; i < height.length; i++) {
while (stack.length > 0 && height[stack.at(-1)] < height[i]) {
const bottom = stack.pop(); // the "floor" of the pocket
if (stack.length === 0) break; // no left wall
const left = stack.at(-1); // left boundary
const right = i; // right boundary (current bar)
const width = right - left - 1;
const depth = Math.min(height[left], height[right]) - height[bottom];
water += width * depth;
}
stack.push(i);
}
return water;
}
console.log(trap([0,1,0,2,1,0,1,3,2,1,2,1])); // 6
console.log(trap([4,2,0,3,2,5])); // 9Problem 3 — Largest Rectangle in Histogram
LeetCode 84. Find the area of the largest rectangle that can be formed in a histogram.
The key idea: for each bar, the rectangle it can anchor extends leftward and rightward until it hits a shorter bar. Use a monotonically increasing stack of indices. When a bar shorter than the stack top arrives, pop and compute the rectangle whose height is the popped bar.
function largestRectangleArea(heights) {
const stack = []; // monotonically increasing indices
let maxArea = 0;
// Append a sentinel 0 to flush all remaining bars at the end
const h = [...heights, 0];
for (let i = 0; i < h.length; i++) {
while (stack.length > 0 && h[stack.at(-1)] > h[i]) {
const height = h[stack.pop()];
const width = stack.length > 0 ? i - stack.at(-1) - 1 : i;
maxArea = Math.max(maxArea, height * width);
}
stack.push(i);
}
return maxArea;
}
console.log(largestRectangleArea([2,1,5,6,2,3])); // 10
console.log(largestRectangleArea([2,4])); // 4Problem 4 — Sum of Subarray Minimums
LeetCode 907. Find the sum of the minimum of every contiguous subarray of arr.
For each element arr[i], count the number of subarrays for which arr[i] is the minimum.
The contribution of arr[i] is:
arr[i] × (left_distance) × (right_distance)
where left_distance is how far left you can go before hitting a smaller (or equal) element,
and right_distance is how far right you can go before hitting a strictly smaller element.
Use a monotonic stack to compute both in O(n).
function sumSubarrayMins(arr) {
const MOD = 1_000_000_007n;
const n = arr.length;
const left = new Array(n); // distance to previous smaller or equal element
const right = new Array(n); // distance to next strictly smaller element
// Previous smaller or equal — monotonically increasing stack
const stack1 = [];
for (let i = 0; i < n; i++) {
while (stack1.length > 0 && arr[stack1.at(-1)] >= arr[i]) stack1.pop();
left[i] = stack1.length > 0 ? i - stack1.at(-1) : i + 1;
stack1.push(i);
}
// Next strictly smaller — monotonically increasing stack from right
const stack2 = [];
for (let i = n - 1; i >= 0; i--) {
while (stack2.length > 0 && arr[stack2.at(-1)] > arr[i]) stack2.pop();
right[i] = stack2.length > 0 ? stack2.at(-1) - i : n - i;
stack2.push(i);
}
let total = 0n;
for (let i = 0; i < n; i++) {
total = (total + BigInt(arr[i]) * BigInt(left[i]) * BigInt(right[i])) % MOD;
}
return Number(total);
}
console.log(sumSubarrayMins([3,1,2,4])); // 17
// subarrays: [3]=3, [1]=1, [2]=2, [4]=4,
// [3,1]=1, [1,2]=1, [2,4]=2,
// [3,1,2]=1, [1,2,4]=1, [3,1,2,4]=1 → sum=17Monotonic Deque — Sliding Window Maximum
LeetCode 239. Find the maximum value in every sliding window of size k.
A monotonic deque (double-ended queue) maintains indices in decreasing order of their values. The front of the deque is always the index of the current window maximum.
function maxSlidingWindow(nums, k) {
const deque = []; // indices, values decrease from front to back
const result = [];
for (let i = 0; i < nums.length; i++) {
// Remove indices that are out of the current window
while (deque.length > 0 && deque[0] < i - k + 1) deque.shift();
// Remove indices whose values are smaller than nums[i]
// (they can never be the max for any future window)
while (deque.length > 0 && nums[deque.at(-1)] < nums[i]) deque.pop();
deque.push(i);
// Start recording results once the first full window is formed
if (i >= k - 1) result.push(nums[deque[0]]);
}
return result;
}
console.log(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3));
// [3,3,5,5,6,7]Practice Problems
LeetCode 496 — Next Greater Element I
LeetCode 503 — Next Greater Element II (circular array)
LeetCode 739 — Daily Temperatures
LeetCode 42 — Trapping Rain Water
LeetCode 84 — Largest Rectangle in Histogram
LeetCode 85 — Maximal Rectangle (histogram row by row)
LeetCode 907 — Sum of Subarray Minimums
LeetCode 239 — Sliding Window Maximum (monotonic deque)