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-EQUAL (or none if empty)
    stack.push(i);
  }
  // anything left on the stack has no next greater element
}

Ties: with these strict pop tests, the top you read after popping is the previous greater-or-equal (or smaller-or-equal) element. Pop on equal values too (<= or >=) when the previous element must be strictly greater or strictly smaller; the pop-time answer then becomes next greater-or-equal, so a single pass cannot make both sides strict.

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] non-increasing (equal values stay on the stack)

  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;
}

Daily Temperatures, Next Greater Element I and Stock Span

Three of the most common warm-ups are the template above with a different thing written at pop time or push time. In each case the stack holds indices (or, when the values are distinct and positions are not needed, values) whose answer is still pending.

Daily Temperatures asks how many days you wait for a warmer day. The answer for day j is the distance to its next greater element, i - j, written when j is popped.

function dailyTemperatures(temperatures) {
  const wait = new Array(temperatures.length).fill(0); // 0 means "never warmer"
  const stack = [];
  for (let i = 0; i < temperatures.length; i++) {
    while (stack.length && temperatures[stack[stack.length - 1]] < temperatures[i]) {
      const j = stack.pop();
      wait[j] = i - j;
    }
    stack.push(i);
  }
  return wait;
}

Dry run: [73, 74, 75, 71, 69, 72, 76, 73]

Indices 6 and 7 are still on the stack at the end and keep their 0. The result is [1, 1, 4, 2, 1, 1, 0, 0]. O(n) time and O(n) space.

Next Greater Element I gives two arrays: for every value of nums1, a subset of nums2 with distinct values, find the next greater element of that value inside nums2. Compute the answer for every value of nums2 with the stack, store it in a Map, then look up each value of nums1. Because the values are distinct and no positions are needed, the stack can hold values.

function nextGreaterElementI(nums1, nums2) {
  const next = new Map(); // value → its next greater value in nums2
  const stack = [];
  for (const value of nums2) {
    while (stack.length && stack[stack.length - 1] < value) next.set(stack.pop(), value);
    stack.push(value);
  }
  return nums1.map((value) => next.get(value) ?? -1);
}

O(n + m) time. If nums2 could repeat a value, a Map keyed by value would mix up the copies; keep indices on the stack in that case.

Stock Span asks, for each day, how many consecutive days ending today (today included) had a price at most today's. That is the distance back to the previous strictly greater price, so the answer is written at push time, from whatever is left on top after the pops, and the pop test is "less than or equal".

function stockSpans(prices) {
  const spans = [];
  const stack = []; // indices; prices strictly decreasing bottom to top
  for (let i = 0; i < prices.length; i++) {
    while (stack.length && prices[stack[stack.length - 1]] <= prices[i]) stack.pop();
    spans.push(stack.length ? i - stack[stack.length - 1] : i + 1);
    stack.push(i);
  }
  return spans;
}

Dry run: [100, 80, 60, 70, 60, 75, 85]

The spans are [1, 1, 1, 2, 1, 4, 6]. The online version (a class with a next(price) method that is called once per day) keeps the same stack, but stores { price, day } pairs and a day counter, since there is no array to index into. Each call is O(1) amortised. Note the symmetry with Daily Temperatures: one writes a distance forward at pop time, the other a distance backward at push time.

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 strictly increasing bottom to top (>= pops equal heights)
  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

Dry run: largestRectangleArea([2, 1, 5, 6, 2, 3]) — the same array as the figure above

Row three is the whole problem: popping the 6 first (width 1, area 6) looks smaller, but the very next pop of the 5 reaches back to left = 2 because the 6 is already gone from the stack — the rectangle of height 5 spans both index 2 and index 3. That's the payoff of storing indices, not values: the width of a popped bar's rectangle depends on what's left standing, which changes after every pop.

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 non-increasing bottom to top (equal heights stay)
  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.

Sum of Subarray Minimums: count the windows each element rules

Add up the minimum of every contiguous subarray. There are O(n²) subarrays, so listing them is too slow for large n. Turn the sum around: sum = Σ arr[i] × (the number of subarrays whose minimum is arr[i]). This is the contribution technique. A subarray with minimum at position i starts somewhere among the positions that are reachable to the left without meeting a smaller value, and ends somewhere reachable to the right, so the count is leftCount × rightCount. Those two extents are the distances to the previous smaller and the next smaller element, which one monotonic stack produces.

Ties need a rule, or equal values would claim the same subarray twice. Decide that a subarray belongs to its leftmost minimum. Then on the left, an equal value blocks the extent (the equal one is more to the left and wins); on the right, an equal value does not block it. Strict on one side and non-strict on the other is the asymmetry that makes every subarray count exactly once.

function sumSubarrayMins(arr) {
  const MOD = 1000000007;
  const stack = []; // indices; values non-decreasing bottom to top, so a pop means a strictly smaller value arrived
  let total = 0;

  for (let i = 0; i <= arr.length; i++) {
    const current = i === arr.length ? -Infinity : arr[i]; // sentinel drains the stack
    while (stack.length && arr[stack[stack.length - 1]] > current) {
      const mid = stack.pop();
      const leftBound = stack.length ? stack[stack.length - 1] : -1; // previous element that is smaller or EQUAL
      const leftCount = mid - leftBound;  // starts: leftBound + 1 .. mid
      const rightCount = i - mid;         // ends: mid .. i - 1 (i is the next STRICTLY smaller)
      total = (total + arr[mid] * leftCount * rightCount) % MOD;
    }
    stack.push(i);
  }
  return total;
}

Dry run: sumSubarrayMins([3, 1, 2, 4])

The total is 3 + 6 + 4 + 4 = 17, which matches the 10 subarrays' minimums added by hand. Tie check on [2, 2]: the first 2 gets 1 start × 2 ends (windows [2] and [2, 2]) = 2 windows, the second gets 1 × 1, giving 2 × 2 + 2 × 1 = 6, the correct sum of 2 + 2 + 2. If both sides were strict the pair window would be counted twice (total 8); if both sides were non-strict it would be counted zero times (total 4).

O(n) time and O(n) space. The product arr[mid] * leftCount * rightCount stays below 2⁵³ for the usual limits (values and n up to about 3 × 10⁴); if both could be around 10⁹ you would need BigInt or a modular multiply. The same recipe with "maximum" instead of "minimum" gives Sum of Subarray Ranges as max-sum minus min-sum.

Lexicographic stacks: Remove K Digits and Remove Duplicate Letters

A monotonic stack also builds the smallest string by deleting characters. The idea: scan left to right; if the new character is smaller than the one on top, then keeping the larger character earlier makes the result larger, so delete it if you are allowed to. The stack ends up non-decreasing, which is the lexicographic minimum.

Remove K Digits: delete exactly k digits from a number string to make the smallest possible number.

function removeKdigits(num, k) {
  const stack = [];
  for (const digit of num) {
    while (k > 0 && stack.length && stack[stack.length - 1] > digit) {
      stack.pop(); // a larger digit earlier in the number loses to a smaller one that follows
      k--;
    }
    stack.push(digit);
  }
  while (k > 0) { stack.pop(); k--; } // still need deletions: the end holds the largest digits

  let start = 0;
  while (start < stack.length - 1 && stack[start] === "0") start++; // strip leading zeros, keep one digit
  const result = stack.slice(start).join("");
  return result === "" ? "0" : result;
}

Dry run: removeKdigits("1432219", 3)

The answer is "1219". Three details lose offers: forgetting the leftover deletions ("12345" with k = 2 never pops in the loop and must lose its last two digits, giving "123"), forgetting to strip leading zeros ("10200" with k = 1 becomes "0200" before stripping, "200" after), and returning an empty string instead of "0" when everything is deleted.

Remove Duplicate Letters: remove repeated letters so that each letter of the string appears exactly once and the result is the smallest in lexicographic order. The same greedy applies with one extra rule: you may pop a larger letter only if it appears again later, because otherwise popping it would lose that letter forever. Track each letter's last index and which letters are already on the stack.

function removeDuplicateLetters(s) {
  const last = new Map();
  for (let i = 0; i < s.length; i++) last.set(s[i], i);

  const inStack = new Set();
  const stack = [];
  for (let i = 0; i < s.length; i++) {
    const ch = s[i];
    if (inStack.has(ch)) continue; // already placed, in the best position found so far
    while (stack.length && stack[stack.length - 1] > ch && last.get(stack[stack.length - 1]) > i) {
      inStack.delete(stack.pop()); // bigger, and it will come again later, so it can wait
    }
    stack.push(ch);
    inStack.add(ch);
  }
  return stack.join("");
}

Dry run: removeDuplicateLetters("cbacdcbc")

The answer is "acdb". O(n) time, because each character is pushed and popped at most once, with O(alphabet) extra space for the two tables. The pattern "pop while the top is worse and it is safe to lose" covers both problems; what "safe" means is the only thing that changes (a remaining deletion budget, or a later copy of the same letter).

132 pattern: a stack that remembers the best "2"

Is there a triple of positions i < j < k with nums[i] < nums[k] < nums[j]? Call the three values "1", "3" and "2" after their relative sizes. A cubic search tries every triple. Scan from the right instead, and keep two things: a decreasing stack of values that could play "3", and third, the largest value known to be a valid "2" (some value that has a strictly larger value on its left, to the right of the scan point). When the scan reaches a new element that is smaller than third, it is a valid "1" and the answer is yes.

function find132pattern(nums) {
  let third = -Infinity; // the best "2" so far: popped values are smaller than a later "3" to their left
  const stack = [];      // candidate "3"s, decreasing bottom to top (equal values stay)
  for (let i = nums.length - 1; i >= 0; i--) {
    if (nums[i] < third) return true; // nums[i] is the "1": it is below a "2" that sits under a bigger "3"
    while (stack.length && stack[stack.length - 1] < nums[i]) third = stack.pop();
    stack.push(nums[i]);
  }
  return false;
}

Dry run: [3, 1, 4, 2]

O(n) time and O(n) space. Why third only ever grows: a value is pushed only if it is not below third (otherwise we would have returned), so every later pop is at least third. The comparisons are strict on both sides because the pattern needs 1 < 2 < 3; with <= the array [1, 2, 2] would wrongly succeed. Scanning left to right with the same ideas needs a prefix-minimum array, and the right-to-left stack version avoids it.

Car Fleet: sort by position, keep a stack of arrival times

Cars drive toward a target on a single lane and cannot pass; a faster car that catches a slower one slows to its speed and from then on they travel as one fleet. Count the fleets that reach the target. The key observation is that only arrival times matter. Sort the cars by position, closest to the target first. A car's own time is (target - position) / speed. If it is no more than the time of the fleet in front, it catches up (or arrives together with it) and merges; if it is strictly more, it is slower than everything ahead and forms a new fleet, which the stack records.

function carFleet(target, position, speed) {
  const order = position.map((_, i) => i).sort((a, b) => position[b] - position[a]); // nearest to the target first
  const fleetTimes = []; // strictly increasing: each fleet is slower than the one in front
  for (const i of order) {
    const time = (target - position[i]) / speed[i];
    if (fleetTimes.length === 0 || time > fleetTimes[fleetTimes.length - 1]) fleetTimes.push(time);
  }
  return fleetTimes.length;
}

Dry run: target = 12, position = [10, 8, 0, 5, 3], speed = [2, 4, 1, 1, 3]

The answer is 3. The cost is the sort, O(n log n). Since a car only ever compares with the last fleet time, a single running maximum would do instead of a stack; the stack framing shows the family resemblance (a pending element is absorbed by a stronger one) and is easier to extend. Equal times always compare equal here, because division of the same rational gives the same double. In principle two different times could round to the same double when positions and speeds are huge; if the limits allow that, compare cross-multiplied integers instead.

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] strictly decreasing front to back (<= pops equal values)
  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 or equal to nums[i] can never be a max again: nums[i] is newer AND at least as big
    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.

Deque with prefix sums: shortest subarray with sum at least K

Find the length of the shortest non-empty subarray with sum at least k, where the array may contain negative numbers. The sliding window from the earlier chapter fails here: with positive numbers, growing the window raises the sum and shrinking lowers it, so a two-pointer rule is valid. With negatives, adding an element can lower the sum and removing one can raise it, so neither pointer has a safe move.

Switch to prefix sums, where prefix[j] - prefix[i] >= k for i < j is the condition, and keep a deque of candidate start indices i. Two observations prune the deque. First, if some start i already satisfies the condition for the current end j, record j - i and discard i for good: every later end gives a longer subarray from i. Second, if the new prefix[j] is at most the prefix at the back of the deque, the back start can never beat j: j is closer to every future end and has a prefix that is no larger, so it gives at least as large a sum. Popping those keeps the deque's prefix values increasing.

function shortestSubarray(nums, k) {
  const n = nums.length;
  const prefix = new Array(n + 1).fill(0);
  for (let i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];

  const deque = new Array(n + 1); // indices into prefix; head and tail replace shift() and pop()
  let head = 0, tail = 0;
  let best = Infinity;

  for (let j = 0; j <= n; j++) {
    while (head < tail && prefix[j] - prefix[deque[head]] >= k) {
      best = Math.min(best, j - deque[head]); // this start is finished: it cannot do better later
      head++;
    }
    while (head < tail && prefix[deque[tail - 1]] >= prefix[j]) tail--; // dominated starts
    deque[tail++] = j;
  }
  return best === Infinity ? -1 : best;
}

Dry run: shortestSubarray([2, -1, 2], 3), prefix = [0, 2, 1, 3]

The answer is 3 (the whole array). Each index enters the deque once and leaves once, so the time is O(n) and the space is O(n) for the prefix array. Using shift() instead of a head pointer would hide an O(n) inside the loop, as discussed in the deque section. The structure is the deque of the sliding-window maximum, with two differences: values are prefix sums, and the front is also popped on a success, not only when it falls out of a fixed-size window.

Deque with DP: Jump Game VI

You start at index 0 and may jump forward by 1 to k steps; the score is the sum of the values you land on, including both ends. Find the maximum score at the last index. The DP is dp[i] = nums[i] + max(dp[i - k .. i - 1]), a maximum over a window of the last k DP values. Computing each maximum by scanning costs O(n · k); but "maximum of every window of size k" is the sliding window maximum. Keep a deque of indices whose DP values decrease, take the front as the window maximum, and push each new dp[i] after popping the smaller values behind it.

function maxResult(nums, k) {
  const n = nums.length;
  const dp = new Array(n);
  dp[0] = nums[0];
  const deque = [0]; // indices; dp values strictly decreasing from head to tail
  let head = 0;

  for (let i = 1; i < n; i++) {
    if (deque[head] < i - k) head++; // the front can no longer reach i
    dp[i] = nums[i] + dp[deque[head]];  // the best place to jump from
    while (deque.length > head && dp[deque[deque.length - 1]] <= dp[i]) deque.pop();
    deque.push(i);
  }
  return dp[n - 1];
}

Dry run: maxResult([1, -1, -2, 4, -7, 3], 2)

The answer is 7, along the path 0, 1, 3, 5 (values 1, -1, 4, 3). O(n) time, O(n) space. The same trick speeds up any DP whose transition is "best of the previous k states": the deque holds dominated-free candidates, and the front is the maximum. When the transition takes a minimum, flip the comparison. The DP chapters mention this as the monotone-deque optimisation.

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
• "How many days until," "how many consecutive days up to now" → distances: write i - j at pop time (Daily Temperatures) or i - top at push time (Stock Span)
• "Sum over all subarrays of their min or max" → the contribution technique: each element times (left extent × right extent), with strict on one side and non-strict on the other to break ties
• "Smallest result after deleting characters or digits," in order → a stack that pops a worse top while it is allowed to lose it (a budget of K, or a later copy)
• A pattern like "small, big, medium" over positions → scan from the end with a decreasing stack and remember the last popped value
• Moving things that merge when a faster one catches a slower one → sort by position and compare arrival times
• A sliding window on an array with negatives and a "sum at least K" target → prefix sums with a monotonic deque of candidate starts
• A DP of the form "best of the previous k states plus a cost" → a monotonic deque over the DP values
• 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