Stack • Monotonic Stack

Next Greater Element (NGE)

Given an array, find the first strictly greater element that is to the right of each element. If none exists, return -1. This is the classic Monotonic Stack problem.

Try Interactive Simulator

Right-to-Left Traversal

By traversing backwards, we process the elements that appear on the "right side" first, storing them in the stack for future leftward elements to query.

The Pops

If the stack's top element is `<= nums[i]`, we pop it. Why? Because `nums[i]` is both LARGER and MORE TO THE LEFT. It completely "blocks" the popped element from ever being the NGE for anything further left!

The Pushes

After finding the NGE from the stack, we push `nums[i]` onto the stack. The stack naturally maintains a Monotonic Decreasing order.

4

-

12

-

5

-

3

-

1

-

2

-

6

-

Top row: Array | Bottom row: NGE Result

Monotonic Decreasing Stack

Empty

Code Tracker

:::

1let stack = []; let result = new Array(n).fill(-1);

2for (let i = n - 1; i >= 0; i--) {

3 while (stack.length > 0 && stack[stack.length - 1] <= nums[i]) {

4 stack.pop();

5 }

6 if (stack.length > 0) {

7 result[i] = stack[stack.length - 1];

8 }

9 stack.push(nums[i]);

10}

11return result;