data structures · linear · O(n) amortized (≤ 2n total pushes + pops)

Monotonic Stack

A monotonic stack is a plain Stack — the exact same push/pop/peek primitive — used with one added rule: before every push, pop off anything already on the stack that would break a chosen order (values kept decreasing, or increasing, from bottom to top). That single invariant turns a question that looks like it needs to check every pair — for every index, scan forward until something bigger turns up — into one O(n) left-to-right pass that answers it for every index at once: what's the next larger value to the right? The naive way resolves one index at a time by scanning forward until it finds something bigger, in the worst case touching almost the whole rest of the array for each one. The stack instead resolves an index's answer the instant a bigger value turns up anywhere later in the same single scan, and never looks at that index again.

Try it

Each column is index:value. Step through the scan: the stack (bottom → top) holds indices whose answer isn't known yet; a push adds the current index, and every pop before it resolves one earlier index's answer. The "non-strict" toggle changes what counts as "greater" — try it on the duplicates preset, where it changes a real answer.

preset

array

non-strict — next greater or equal, instead of strictly greater

array

stack (bottom → top)

next greater value found so far

Reference implementation

function nextGreaterElements(arr, strict = true) {
  const n = arr.length;
  const result = new Array(n).fill(-1);
  const stack = []; // indices only, values stay in decreasing (or non-increasing) order bottom to top

  for (let i = 0; i < n; i++) {
    while (
      stack.length &&
      (strict ? arr[stack[stack.length - 1]] < arr[i] : arr[stack[stack.length - 1]] <= arr[i])
    ) {
      const j = stack.pop();
      result[j] = arr[i]; // arr[i] is index j's answer
    }
    stack.push(i);
  }

  return result; // indices still on the stack at the end keep their -1 default: nothing greater exists to their right
}

The stack holds indices, not values — the value is always one array lookup away (arr[j]), but the index is the only way to write the answer into the right slot of result, and the only way to compute a distance later if a problem needs "how far away," not just "what value" (see Pitfalls below).

Complexity

Time: the code above is a for loop with a nested while, which looks like it could be O(n²) — but it isn't. Every index is pushed exactly once (once per iteration of the outer loop) and popped at most once (a popped index is never pushed again), so the total number of pushes plus pops across the entire scan is at most 2n, regardless of how the values are arranged. That makes the whole scan O(n) amortized, the same style of proof as a dynamic array's amortized O(1) push. Space: O(n) worst case for the stack (a strictly decreasing array never pops anything until the very end).

The bound holds regardless of input shape, but that doesn't mean the stack is always doing less raw work than the brute-force O(n²) alternative (compare each index against every later one until something bigger turns up, or the array ends) — only that it never does asymptotically more. Measured directly on the array this page loads by default, for both the strict and non-strict comparison:

preset	n	stack ops (push + pop)	brute-force comparisons
duplicates (strict)	9	13	16
duplicates (non-strict)	9	14	14
worst case for brute force	10	19	45
best case for brute force	10	19	9

The "worst case" row is a falling run followed by one big value at the very end — brute force has to scan almost to the end from nearly every starting index before it finds something bigger, while the stack still does at most 2n work no matter what. The "best case" row is the honest counter-example: on an already-increasing array, brute force finds every answer in exactly one comparison (9 total for n = 10), while the stack still pays close to its full 2n bound (19) — pushing and then almost immediately popping every index. The stack's real advantage is the guarantee, not winning on every individual input; an array that's already sorted the easy way is one input where brute force is genuinely cheaper.

Pitfalls

Strict vs. non-strict changes real answers on duplicate values, silently. "Next strictly greater" and "next greater or equal" agree everywhere except where the array repeats a value. On this page's default preset, [2, 5, 2, 6, 1, 4, 4, 3, 2], index 5 holds a 4 and the only later value is another 4 at index 6: strictly-greater says that's not good enough, so index 5's answer is -1 (nothing greater exists). Non-strict counts an equal value as a match, so index 5's answer becomes 4 instead. Neither comparison is "the bug" in general — plenty of real problems want one or the other — but copying a non-strict solution into a spot that needed strict comparison (or the reverse) changes an answer from correct to wrong with no error, no crash, and no symptom on an array that happens to have no duplicates in the wrong place. Toggle the checkbox above on the duplicates preset and step to index 5 to see both answers directly.

Storing values instead of indices loses information a lot of real problems need. This page's stack holds indices specifically so it can write into result[j] and, if a problem asks for it, compute a distance (i - j). A version that pushes values instead of indices can still answer "what's the next larger value," but it can never answer "how many positions away is it" — a classic version of this exact technique, Daily Temperatures (how many days until a warmer day), needs that distance and is unsolvable with a value-only stack no matter how the rest of the logic is written.

Scanning the wrong direction finds the wrong neighbor. This page scans left-to-right and finds, for each index, the next qualifying value to its right. Running the identical pop-then-push logic while scanning right-to-left instead finds the next qualifying value to each index's left — a different, equally valid question, but a different answer for almost every index. Confusing the two — for instance wanting "closest smaller value on the left" but scanning forward — is a direction bug, not a comparison bug, and looking only at the comparison operator (< vs <=) won't catch it.

Where it shows up

Daily Temperatures. For each day, how many days until a warmer one — the distance-based version mentioned above, the reason the stack holds indices rather than values.
Largest Rectangle in Histogram. For each bar, the nearest shorter bar on its left and right bound how wide a rectangle can extend through it — both bounds are a monotonic-stack scan (one left-to-right, one right-to-left, or one pass tracking both).
Stock Span Problem. For each day's price, how many consecutive prior days had a price no higher than today's — the same "pop while smaller, then push" shape, counting span instead of recording a value.
Trapping Rain Water. One standard solution keeps a stack of decreasing wall heights and computes trapped water when a taller wall finally shows up and pops the shorter ones — the same invariant, applied to an accumulating total instead of a per-index answer.
The two-ended sibling: Monotonic Deque. The identical pop-before-push invariant applied from both ends of a Deque instead of one end of a stack, answering a sliding window's max/min instead of a next-greater/next-smaller value — same idea, applied to a window that moves instead of a scan that only grows.

This site's guide, Choosing a Linear Data Structure, places this entry alongside the other seven Linear structures and explains why it doesn't compete with them the way they compete with each other.