Next Greater Element II
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]
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;}