The Monotonic Stack Pattern Explained

Quick Answer

A monotonic stack is a stack kept strictly increasing or strictly decreasing at all times, popping whichever elements would break that order before pushing the new one in. It turns problems like next greater element, daily temperatures, and largest rectangle in a histogram from an O(n²) brute force into O(n), because each element only ever gets pushed and popped once across the entire run.

The Problem: Next Greater Element

For every element in an array, find the first element to its right that is strictly bigger; if none exists, the answer is -1. For [2, 1, 2, 4, 3]: index 0 (value 2) finds 4 first; index 1 (value 1) finds 2; index 2 (value 2) also finds 4; indices 3 and 4 (values 4 and 3) find nothing bigger to their right, so both are -1.

The direct approach nests a loop inside a loop — for each starting index, scan forward until something bigger turns up:

function nextGreaterBrute(nums) {
  const n = nums.length;
  const result = new Array(n).fill(-1);
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if (nums[j] > nums[i]) { result[i] = nums[j]; break; }
    }
  }
  return result;
}

Worst case — a strictly decreasing array, where nothing finds an answer until the scan has already run to the end for every single starting point — this is O(n²). The nested loop is doing a lot of repeated, wasted comparisons that a smarter data structure can avoid entirely.

The Insight: Only Keep What Might Still Win

Process the array left to right while maintaining a stack of indices whose "next greater" answer isn't known yet. When a new number is seen, it might be exactly the answer for some of the numbers already waiting on the stack — specifically, every one of them that is smaller than the new number. So pop them off one at a time, record the new number as their answer, and keep popping until the stack's top is bigger than the new number (or the stack runs empty). Then push the new index on.

Because of how that popping rule works, the stack always holds values in decreasing order from bottom to top — any time it wouldn't have been, the offending element would already have been popped by an earlier step. That invariant is exactly what "monotonic" refers to. It's worth storing indices on the stack rather than raw values, since the result array needs to know which position to write into.

The complexity works out to O(n) overall, even though there's a while loop nested inside a for loop, because every index is pushed exactly once and popped at most once across the entire run — the total number of pop operations, summed over the whole algorithm, can never exceed n.

The Monotonic Stack in Code

function nextGreater(nums) {
  const n = nums.length;
  const result = new Array(n).fill(-1);
  const stack = []; // indices; nums at these indices decrease bottom to top

  for (let i = 0; i < n; i++) {
    while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
      const idx = stack.pop();
      result[idx] = nums[i];
    }
    stack.push(i);
  }
  return result;
}

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

Tracing it: at i=0 (2) the stack is empty, so index 0 is pushed. At i=1 (1), 1 isn't bigger than the 2 already on the stack, so it's just pushed too — stack is now [0, 1]. At i=2 (2), the top of the stack (index 1, value 1) is smaller, so it's popped and result[1] = 2; the new top (index 0, value 2) isn't smaller than 2, so popping stops there, and index 2 is pushed. At i=3 (4), both remaining stack entries (values 2 and 2) are smaller, so both get popped with result[2] = 4 and result[0] = 4, leaving an empty stack that then gets index 3 pushed onto it. At i=4 (3), 3 isn't bigger than 4, so it's simply pushed. Indices 3 and 4 are never popped, so they keep their default of -1 — matching the verified output exactly.

The Gotcha: Store Indices, Not Values

A mistake that looks harmless until duplicate values enter the picture: pushing the raw values onto the stack instead of their indices, then trying to recover "which index did this come from" after popping, usually with something like nums.indexOf(value). With duplicate values, indexOf always returns the position of the first matching occurrence — not necessarily the one that's actually being resolved.

// value-based stack — looks reasonable, is wrong on any input with duplicates
function nextGreaterBuggy(nums) {
  const n = nums.length;
  const result = new Array(n).fill(-1);
  const stack = [];
  for (let i = 0; i < n; i++) {
    while (stack.length && stack[stack.length - 1] < nums[i]) {
      const val = stack.pop();
      const idx = nums.indexOf(val); // wrong index when val repeats
      result[idx] = nums[i];
    }
    stack.push(nums[i]);
  }
  return result;
}

nextGreaterBuggy([2, 1, 2, 4, 3]);
// [4, 2, -1, -1, -1]  -- wrong at index 2
nextGreater([2, 1, 2, 4, 3]);
// [4, 2, 4, -1, -1]   -- correct

Both versions were run on the exact same array containing the repeated value 2. When 4 arrives and pops the two 2's off the value-based stack, nums.indexOf(2) returns index 0 both times — so index 0 gets written twice and index 2's slot in the result array is never touched, staying stuck at the default -1. This isn't an edge case that shows up occasionally; the value-based version is wrong on any input containing a repeated value, which is common enough that it will surface quickly in practice. Storing indices sidesteps the entire problem, since indices are always unique by definition.

A Variant: Daily Temperatures

A close relative asks for a distance instead of a value: given daily temperatures, return for each day how many days must pass until a warmer day arrives, or 0 if it never happens. The stack logic is identical — still a monotonic decreasing stack — only the payload recorded on each pop changes, from the winning value to i - idx, the gap between the two positions.

function dailyTemperatures(temps) {
  const n = temps.length;
  const result = new Array(n).fill(0);
  const stack = [];
  for (let i = 0; i < n; i++) {
    while (stack.length && temps[stack[stack.length - 1]] < temps[i]) {
      const idx = stack.pop();
      result[idx] = i - idx;
    }
    stack.push(i);
  }
  return result;
}

dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73]);
// [1, 1, 4, 2, 1, 1, 0, 0]

Run against that exact input, the result matches the expected sequence exactly. Notice how little changed from nextGreater — same skeleton, different line inside the while loop. Once the underlying pattern is recognized, adapting it to a new problem statement is close to mechanical.

Where the Monotonic Stack Pattern Shows Up

The same shape underlies several well-known problems: Largest Rectangle in a Histogram (find, for each bar, how far it can extend before hitting a shorter bar on either side), Trapping Rain Water (track bounding walls as the scan proceeds), and the Stock Span Problem (for each day, how many consecutive prior days had a lower or equal price). A related but distinct structure, the monotonic deque, solves sliding-window-maximum problems by allowing pops from both ends instead of just one.

The tell that a problem wants a monotonic stack: "for every element, find the nearest element to its left or right that is bigger (or smaller) than it." Any time a brute-force solution to that shape involves a nested loop scanning outward from every position, a monotonic stack is very likely the O(n) fix — worth checking before reaching for anything heavier.

Frequently Asked Questions