Stack • Monotonic Stack

Previous Smaller Element (PSE)

Given an array, find the first strictly smaller element to the left of each element. This pairs with NSE to form the basis of advanced algorithms.

Try Interactive Simulator

The Perfect Pair

Previous Smaller Element (PSE) and Next Smaller Element (NSE) are frequently used together. By knowing the boundary on the left (PSE) and the right (NSE), you can easily calculate the span or area over which an element is the absolute minimum.

Increasing Stack

Just like NSE, PSE requires a Monotonic Increasing Stack. We pop elements that are `>= nums[i]`. The only difference is we traverse from Left to Right.

Why it matters

Used heavily in "Largest Rectangle in Histogram" and "Sum of Subarray Minimums".

4

-

8

-

5

-

2

-

25

-

Top row: Array | Bottom row: PSE Result

Monotonic Increasing Stack

Empty

Code Tracker

:::

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

2for (let i = 0; i < n; 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;