Maintain a stack or queue in sorted order to answer next-greater and sliding window max in O(n).
A monotonic stack keeps elements in strictly increasing or decreasing order. When a new element breaks the order, we pop and process. This answers "next greater element", "previous smaller element", and similar range queries in O(n) instead of O(nĀ²).
O(n) ā each element pushed and popped at most once
O(n) for the stack
Learn the core patterns in this topic. Each block explains when to use the pattern, the intuition behind it, and a compact code example.
Use this when the problem asks for the next element to the right that is strictly greater than the current element
Maintain a stack of indices in decreasing order of their values. When a new element is larger than the element at the top index, the new element is the answer for that popped index. Push the current index after all pops.
Problem Next Greater Element I. For each element in nums2, pop any index whose value is smaller than the current element and record the answer.
// Monotonic decreasing stack ā Next Greater Element I
function nextGreaterElement(nums1, nums2) {
const nge = {}, stack = [];
for (const n of nums2) {
while (stack.length && stack.at(-1) < n) nge[stack.pop()] = n;
stack.push(n);
}
return nums1.map(n => nge[n] ?? -1);
}Use this as the standard application of a monotonic decreasing stack where the answer for each element is a distance rather than a value
Store indices on the stack, and when a warmer temperature is found, compute the day difference as i - popped index.
Problem Daily Temperatures. Push index i; when temps[i] > temps[stack top], pop and set result[popped] = i - popped.
// Daily temperatures ā decreasing stack of indices, distance answer
function dailyTemperatures(temps) {
const result = new Array(temps.length).fill(0);
const stack = [];
for (let i = 0; i < temps.length; i++) {
while (stack.length && temps[i] > temps[stack.at(-1)]) {
const idx = stack.pop();
result[idx] = i - idx;
}
stack.push(i);
}
return result;
}Use this when you need to know, for each position, the nearest index to its left that holds a smaller value
Maintain a monotonic increasing stack of indices. Before pushing the current index, the stack top is the previous smaller element.
Problem Sum of Subarray Minimums. For each index, the previous smaller boundary is the current stack top (or -1 if empty).
// Previous smaller element ā monotonic increasing stack
function previousSmaller(nums) {
const pse = [], stack = [];
for (let i = 0; i < nums.length; i++) {
while (stack.length && nums[stack.at(-1)] >= nums[i]) stack.pop();
pse.push(stack.length ? stack.at(-1) : -1);
stack.push(i);
}
return pse;
}Use this when you need the number of consecutive days (or elements) to the left that are less than or equal to the current element, known as the stock span problem
As you pop smaller elements the span grows; the span equals the distance from the current index to the remaining stack top.
Problem Stock Span. Pop while the top price is less than or equal to the current price; the span is i minus the new top (or 0 if empty).
// Stock span ā monotonic increasing stack for span widths
function stockSpan(prices) {
const span = [], stack = [];
for (let i = 0; i < prices.length; i++) {
while (stack.length && prices[stack.at(-1)] <= prices[i]) stack.pop();
span.push(stack.length ? i - stack.at(-1) : i + 1);
stack.push(i);
}
return span;
}Use this when you want to compute trapped water by processing horizontal layers rather than column by column
A decreasing stack stores candidate left-wall indices. When a taller bar arrives, the popped bar is the floor, the stack top is the left wall, and the current bar is the right wall. Multiply the bounded height by the width to get the trapped volume.
Problem Trapping Rain Water. Pop the floor bar, check that a left wall still exists, compute height and width, accumulate water.
// Trapping rain water via stack ā horizontal layer approach
function trap(height) {
const stack = [];
let water = 0;
for (let i = 0; i < height.length; i++) {
while (stack.length && height[i] > height[stack.at(-1)]) {
const floor = stack.pop();
if (!stack.length) break;
const h = Math.min(height[stack.at(-1)], height[i]) - height[floor];
const w = i - stack.at(-1) - 1;
water += h * w;
}
stack.push(i);
}
return water;
}Use this when you need the maximum or minimum of every k-width window in a single O(n) pass
A deque stores indices in decreasing order (for max) or increasing order (for min). Before adding a new index, remove from the back any index whose value is dominated by the new element, and remove from the front any index that has fallen outside the window. The front always holds the current window extreme.
Problem Sliding Window Maximum. Evict the front when it is out of range; evict the back while nums[back] <= nums[i]; then the front index is the window max.
// Monotonic deque for sliding window max ā O(n)
function maxSlidingWindow(nums, k) {
const dq = [], res = [];
for (let i = 0; i < nums.length; i++) {
while (dq.length && dq[0] < i - k + 1) dq.shift();
while (dq.length && nums[dq.at(-1)] <= nums[i]) dq.pop();
dq.push(i);
if (i >= k - 1) res.push(nums[dq[0]]);
}
return res;
}