Next Greater Element II

1. Define the problem

Given a circular array (the last element wraps around to be next to the first), return an array where each element is the next number that is greater than it , searching forward through the wraparound if needed. If no greater number exists anywhere, output -1 for that position. Walk the array twice its length using a monotonic stack of indices whose "next greater" is still unknown — whenever a bigger value shows up, it resolves every smaller index still waiting on the stack.

Constraints

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums_i ≤ 10⁹

Example

Inputnums = [1, 2, 1]

Output[2, -1, 2]

Explanation nums₀=1 is followed by 2, so its answer is 2. nums₁=2 has nothing bigger anywhere, even wrapping around, so its answer is -1. nums₂=1 wraps around and finds 2 at index 0.

2. Know the words first

In plain terms

Monotonic stack: A stack kept in strictly decreasing order from bottom to top; anything that would break that order gets popped off first.

3. Visualize the solution

Walk the array twice, resolving a stack of waiting indices

Statuspush

i=0 (index 0, value 1): stack is empty, so just push index 0.

What happens in this step

i = 0, index = 0, value = 1
stack = [] → push 0
stack = [0]
result = [-1, -1, -1]

Step 1 of 6

Steps to visualize

Walk from index 0 up to twice the array length, always looking at index i modulo the length.
While the value on top of the stack is smaller than the current value, pop it and record the current value as its answer.
Only push the actual index onto the stack during the first lap (i less than length) — the second lap just resolves leftovers.
Any index still on the stack when the walk finishes never found a greater value, so its answer stays -1.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Walk the array twice, resolving a stack of waiting indices

Statuspush

i=0 (index 0, value 1): stack is empty, so just push index 0.

What happens in this step

i = 0, index = 0, value = 1
stack = [] → push 0
stack = [0]
result = [-1, -1, -1]

Step 1 of 6

5. Solution

Solution

solution.tsTypeScript

function nextGreaterElements(nums) {
  const n = nums.length;
  const result = new Array(n).fill(-1);
  const stack = [];

  for (let i = 0; i < 2 * n; i++) {
    const index = i % n;

    while (stack.length > 0 && nums[stack[stack.length - 1]] < nums[index]) {
      const top = stack.pop();
      result[top] = nums[index];
    }

    if (i < n) {
      stack.push(index);
    }
  }

  return result;
}

Time: O(n)
Space: O(n)

6. Test cases

Test cases

Input	Expected	Covers
`nums = [1, 2, 1]`	`[2, -1, 2]`	example from the docstring
`nums = [1]`	`[-1]`	smallest valid input: a single element can never beat itself
`nums = [3, 3, 3]`	`[-1, -1, -1]`	every value is equal, so nothing is ever strictly greater, even wrapping around
`nums = [1, 2, 3, 4, 5]`	`[2, 3, 4, 5, -1]`	a strictly increasing array where only the maximum has no answer
`nums = [1, 1, 1]`	`[-1, -1, -1]`	every value equal, so nothing is strictly greater
`nums = [3, -1, 3]`	`[-1, 3, -1]`	negative values and a duplicate boundary value that is not strictly greater than itself

Next Greater Element II