Monotonic Stack

A monotonic stack is a stack that is kept in either strictly increasing or strictly decreasing order from bottom to top. Whenever a new element would violate the ordering, elements are popped until the invariant is restored, and those pops are the answers to the query.

The trick that makes it efficient: every element is pushed once and popped at most once, so the total work across all iterations is O(n) — even though the inner pop-loop looks nested.

Next Greater Element

Given an array of integers, find for each position the index of the next element that is strictly greater. Return -1 where none exists.

We use a decreasing stack (largest on top to smallest at bottom). When a new element nums[i] arrives and is larger than the top, that top has found its answer.

function nextGreaterElement(nums) {
  const result = new Array(nums.length).fill(-1);
  const stack = []; // stores indices, not values

  for (let i = 0; i < nums.length; i++) {
    // pop every index whose value is smaller than the current element
    while (stack.length && nums[stack.at(-1)] < nums[i]) {
      const idx = stack.pop();
      result[idx] = i; // nums[i] is the next greater for idx
    }
    stack.push(i);
  }

  // anything left in the stack has no next greater element (-1 by default)
  return result;
}

const nums = [2, 1, 5, 3, 6, 4];
console.log(nextGreaterElement(nums));
// [2, 2, 4, 4, -1, -1]
// index 0 (val 2) → index 2 (val 5)
// index 1 (val 1) → index 2 (val 5)
// index 2 (val 5) → index 4 (val 6)
// index 3 (val 3) → index 4 (val 6)
// index 4 (val 6) → none
// index 5 (val 4) → none

Increasing vs. Decreasing

To find the next smaller element, flip the comparison: pop when nums[stack.at(-1)] > nums[i].

Complexity

Each index enters the stack once and leaves at most once. The while-loop pops happen across all iterations combined, not per iteration, which is why the total time is O(n) rather than O(n²).

Classic Problems That Use This Pattern

• Largest Rectangle in Histogram — pop when a shorter bar is encountered; the popped bar’s height times the computed width is a candidate answer.
• Daily Temperatures — exactly the next-greater pattern on temperature values; return distances instead of indices.
• Trapping Rain Water — a two-pointer approach is simpler, but a monotonic stack also solves it in one pass.
• Sliding Window Maximum — a monotonic deque (covered in the Deque lesson) extends this idea to a rolling window.

Up Next

Move from last-in-first-out to first-in-first-out and see why a naive array queue is O(n) per dequeue.