Stack • Monotonic Stack

Next Smaller Element (NSE)

Given an array, find the first strictly smaller element to the right of each element. This uses a Monotonic Increasing Stack.

The Opposite Rule

This is identical to Next Greater Element, but instead of popping elements that are `<= nums[i]`, we pop elements that are `>= nums[i]`.

Because we pop all larger elements before pushing the current element, the stack naturally maintains a strict increasing order from bottom to top.

Next Smaller Element is a critical subroutine used to solve much harder problems like "Largest Rectangle in Histogram" and "Maximal Rectangle".

4

-

8

-

5

-

2

-

25

-

Top row: Array | Bottom row: NSE Result

Monotonic Increasing 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;