Next Greater Element II

Medium

Problem

The array is circular: the element after the last one is the first. For each element, return the first greater element found by moving forward (wrapping around), or −1 if there is none.

Example 1

Input:  [1, 2, 1]
Output: [2, -1, 2]

The last 1 wraps around to find 2.

Test cases

Case 1

Input:    [1,2,1]
Expected: [2,-1,2]

Case 2

Input:    [1,2,3,4,3]
Expected: [2,3,4,-1,4]

Case 3

Input:    [5,5]
Expected: [-1,-1]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Monotonic stack over two passes

Time O(n)Space O(n)

Circular array: iterate 2n times using i % n so elements near the end can see the start. Only push during the first pass.

function nextGreaterElements(nums) {
const n = nums.length, res = new Array(n).fill(-1), st = [];
for (let i = 0; i < 2 * n; i++) {
const x = nums[i % n];
while (st.length && x > nums[st[st.length - 1]]) res[st.pop()] = x;
if (i < n) st.push(i);
}
return res;
}