Stack • Monotonic Stack

Next Greater Element (Circular Array)

How do you find the Next Greater Element when the array is circular? (i.e., the next element after the last is the first element).

Try Interactive Simulator

The "Double Array" Trick

A circular array can be simulated by simply duplicating the array and placing the copy right next to the original: `[1, 2, 1]` becomes `[1, 2, 1, 1, 2, 1]`.

Virtual Duplication

Instead of actually using extra memory to duplicate the array, we can just run our loop from `2*N - 1` down to `0` and use the modulo operator `i % N` to access elements.

Two Phases

When `i >= N`, we are just pushing elements onto the stack so that when `i < N`, the stack is already populated with the "circular" elements that would appear to the right.

1

-

2

-

1

-

1

2

1

Solid boxes = Real Array | Dashed boxes = Virtual (Circular) Array

Monotonic Stack

Empty

Code Tracker

:::

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

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

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

4 stack.pop();

5 }

6 if (i < n) {

7 if (stack.length) res[i] = stack[stack.length - 1];

8 }

9 stack.push(nums[i % n]);

10}

11return res;

Next Greater Element Circular

Next Greater Element Circular

Next Greater Element (Circular Array)

The "Double Array" Trick

Virtual Duplication

Two Phases

Next Greater Element (Circular Array)

The "Double Array" Trick

Virtual Duplication

Two Phases