Monotonic stack & queue in depth

The insight: some elements become permanently useless

Suppose you're scanning left to right looking for each element's next greater element. You reach value 7 and the pending element behind it is a 3. That 3 is finished — 7 is its answer, and no later element can ever be its answer instead. But more than that: the 3 is now useless to everyone. Any future element looking backward for something bigger will hit the 7 before it reaches the 3. So the 3 can be discarded entirely.

Do this consistently and the pending set is always sorted — a monotonic stack. You never search it, never sort it, never scan it: you only pop from the top while the invariant is violated. Each element is pushed exactly once and popped at most once, so the total work across the whole scan is O(n), even though the inner while loop can pop many elements on a single step.

The canonical shape

// The template. Two decisions define every variant:
//   1. the comparison in the while condition (< vs > vs <= vs >=)
//   2. what you do at pop time vs. at push time
function monotonic(nums) {
  const stack = []; // store INDICES, not values — you almost always need positions

  for (let i = 0; i < nums.length; i++) {
    while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
      const j = stack.pop();
      // nums[i] is j's NEXT GREATER — resolve j here
    }
    // whatever is on top now is i's PREVIOUS GREATER (or none if empty)
    stack.push(i);
  }
  // anything left on the stack has no next greater element
}

Memorize the derivation, not the table: "I want the next bigger thing, so a pending element stops being pending the moment something bigger arrives, so I pop while the top is smaller, so the stack is decreasing." Regenerate it in ten seconds at the whiteboard instead of recalling four near-identical rules under pressure.

Next greater element

// For each element, the first larger value to its right; -1 if none. O(n).
function nextGreater(nums) {
  const res = new Array(nums.length).fill(-1);
  const stack = []; // indices; nums[stack] strictly decreasing

  for (let i = 0; i < nums.length; i++) {
    while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
      res[stack.pop()] = nums[i];
    }
    stack.push(i);
  }
  return res; // leftovers keep their -1 — nothing bigger ever came
}

nextGreater([2, 1, 2, 4, 3]); // [4, 2, 4, -1, -1]

The circular variant ("Next Greater Element II") wraps around the end of the array. The fix is not a second algorithm — just walk the index twice and mod:

function nextGreaterCircular(nums) {
  const n = nums.length;
  const res = new Array(n).fill(-1);
  const stack = [];

  for (let step = 0; step < 2 * n; step++) { // two laps: the second one resolves the wrap-around
    const i = step % n;
    while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
      res[stack.pop()] = nums[i];
    }
    if (step < n) stack.push(i); // only push during the first lap, or indices duplicate
  }
  return res;
}

Largest rectangle in histogram

This is the problem that makes the pattern click. A rectangle of height heights[j] extends left until it hits a strictly shorter bar and right until it hits a strictly shorter bar. So each bar needs its previous smaller and next smaller index — exactly what an increasing stack hands you: i is the right boundary at pop time, and the new stack top is the left boundary.

// O(n) time, O(n) space
function largestRectangleArea(heights) {
  const stack = []; // indices; heights increasing bottom to top
  let best = 0;

  for (let i = 0; i <= heights.length; i++) {
    // SENTINEL: a virtual height-0 bar past the end drains the stack — no cleanup loop
    const h = i === heights.length ? 0 : heights[i];

    while (stack.length && heights[stack[stack.length - 1]] >= h) {
      const height = heights[stack.pop()];
      // left boundary = one past the new top; if the stack emptied, this bar reached index 0
      const left = stack.length ? stack[stack.length - 1] + 1 : 0;
      best = Math.max(best, height * (i - left)); // width = right boundary i, exclusive
    }
    stack.push(i);
  }
  return best;
}

largestRectangleArea([2, 1, 5, 6, 2, 3]); // 10 — the 5 and 6 bars, width 2

Directly on top of this: Maximal Rectangle in a binary matrix. Walk the rows, maintain a running "height of consecutive 1s ending at this row" array, and call largestRectangleArea on it once per row — O(rows × cols) total. Recognizing that a hard 2D problem is this 1D problem run row-by-row is exactly the kind of reduction interviews reward.

Trapping rain water, the monotonic-stack way

You have probably seen the two-pointer solution. The stack version is worth knowing because it computes the water in horizontal layers rather than vertical columns, and it's the same skeleton as the histogram — which means one mental model covers both problems.

// O(n) time, O(n) space — fills water layer by layer
function trap(height) {
  const stack = []; // indices; heights decreasing bottom to top
  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 the basin we're about to fill
      if (!stack.length) break;   // no left wall → water spills off the edge

      const left = stack[stack.length - 1];
      const width = i - left - 1;                                    // strictly between the two walls
      const bounded = Math.min(height[left], height[i]) - height[bottom]; // shorter wall caps the level
      water += width * bounded;
    }
    stack.push(i);
  }
  return water;
}

trap([0,1,0,2,1,0,1,3,2,1,2,1]); // 6

The break when the stack empties is the whole "you need walls on both sides" rule, expressed structurally. And notice bounded subtracts height[bottom]: you're adding only the slab above the previously-filled level, never double-counting a layer you already paid for. The two-pointer solution is O(1) space and is the better final answer — but explaining the layered view first shows you understand why the two-pointer bound works.

Monotonic deque: sliding window maximum

Same invariant, one extra requirement: elements also expire off the front when they fall out of the window. A stack can't do that, so you use a deque — pop from the back to maintain monotonicity, shift from the front to evict stale indices. The front is always the window's maximum because everything smaller behind it was discarded on arrival.

// max of every window of size k — O(n) time, O(k) space
function maxSlidingWindow(nums, k) {
  const dq = []; // indices; nums[dq] decreasing front to back
  const out = [];

  for (let i = 0; i < nums.length; i++) {
    if (dq.length && dq[0] <= i - k) dq.shift(); // front fell out of the window — evict

    // anything smaller than nums[i] can never be a max again: nums[i] is newer AND bigger
    while (dq.length && nums[dq[dq.length - 1]] <= nums[i]) dq.pop();

    dq.push(i);
    if (i >= k - 1) out.push(nums[dq[0]]); // front = current window max
  }
  return out;
}

maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3); // [3, 3, 5, 5, 6, 7]

That last row is the useful boundary: a monotonic deque works because max lets you discard dominated elements forever. If the query were "median of every window," nothing is discardable — you'd need two heaps or an ordered multiset. Knowing why the deque stops working is more valuable than knowing that it works.

See the stack work

Watch the stack stay decreasing. Every index is pushed once and popped at most once, which is the whole argument for O(n) despite the inner while loop.

Recognizing it in an unseen problem

• The literal words "next greater," "next smaller," "previous warmer day," "first element to the right that…" — that's a monotonic stack, unconditionally
• Each element needs its span or boundaries — "how far can this bar/temperature/stock price extend before something bigger stops it" (Daily Temperatures, Stock Span, Largest Rectangle, Maximal Rectangle, Sum of Subarray Minimums)
• The brute force is an O(n²) double loop where the inner loop scans rightward until a condition trips — that inner scan is what the stack amortizes away
• "Maximum/minimum of every window of size k" with a fixed k → monotonic deque. The extra front-eviction is the only difference from a stack
• Distinguish from a plain sliding window: sliding window maintains an aggregate (sum, count, set) that updates in O(1); monotonic structures maintain an ordered candidate set because the aggregate (max, min) can't be undone incrementally when an element leaves
• Distinguish from a heap: use a heap when you need the kth or the median, or when elements arrive without a scan order. Use a monotonic deque when a newer-and-better element makes an older one permanently irrelevant
• Pitfalls: pushing values instead of indices (you'll need positions for widths), the wrong strictness on ties, forgetting the sentinel so the stack never drains, and assuming shift() is free