Monotonic Stack

A monotonic stack answers the question *'for each element, what's the next larger value to its right?'* for every element in a single pass. The stack holds elements still waiting for an answer, kept in decreasing order from bottom to top. When a new value arrives, it pops everything smaller than itself — and each popped element has just found its next greater element: the new value.

The core idea

An element on the stack is one that hasn't yet seen anything bigger to its right. Keeping the stack strictly decreasing means the moment a bigger value appears, all the smaller values sitting above are *resolved at once*. Then the new value is pushed to wait for its own next-greater. Nothing ever gets scanned twice.

1. 1Scan the array left to right, keeping a stack of indices whose values are still unresolved.
2. 2For each new value, pop every stack element smaller than it — the new value is their next greater element.
3. 3Push the new element's index; it now waits for something bigger.
4. 4Anything left on the stack at the end has no greater value to its right → answer -1.

Worked trace — next greater in [2, 1, 2, 4, 3]

1. 12: stack empty → push. Stack (values): [2].
2. 21: 1 < 2 → push. Stack: [2, 1].
3. 32: 2 > 1 → pop 1, its answer is 2. Now top is 2, not strictly less → push. Stack: [2, 2].
4. 44: 4 > 2 → pop, answer 4. 4 > 2 → pop, answer 4. Empty → push. Stack: [4].
5. 53: 3 < 4 → push. Stack: [4, 3].
6. 6End: 4 and 3 remain → both answer -1. Result: [4, 2, 4, -1, -1].

function nextGreater(arr) {
  const res = new Array(arr.length).fill(-1);
  const stack = []; // holds indices, values decreasing
  for (let i = 0; i < arr.length; i++) {
    while (stack.length && arr[i] > arr[stack[stack.length - 1]]) {
      res[stack.pop()] = arr[i]; // i is the next greater
    }
    stack.push(i);
  }
  return res;
}
// nextGreater([2, 1, 2, 4, 3]) === [4, 2, 4, -1, -1]