Next Greater Value in a Circular Sequence

Implement nextGreaterCircular

Given a circular integer array arr (after the last element, the array wraps back to the first), find, for every position, the next element going clockwise that is strictly greater than it — searching at most once all the way around, and returning -1 if none exists. The circularity can be simulated without ever duplicating the array: walk virtual indices from 0 up to 2n-1, mapping each one back into range with i % n. A monotonic decreasing stack of real indices handles the rest exactly as it would for a non-circular array — except now every index effectively gets two laps to find its answer instead of one. The only twist is to stop pushing new indices once the second lap begins (i >= n), since by then every index has already had its one chance to enter the stack. Each real index is still pushed exactly once and popped at most once across the whole walk, so the total work stays O(n) despite covering 2n virtual steps.

Example 1:

Input: arr = [5,3,8,2]

Output: [8,8,-1,5]

Example 2:

Input: arr = [6,1,4,9,2]

Output: [9,4,9,-1,6]

Example 3:

Input: arr = [9,7,5,3,1]

Output: [-1,9,9,9,9]

+ 3 hidden test cases run on Submit.

Constraints:

  • 1 ≤ arr.length ≤ 12
  • 0 ≤ arr[i] ≤ 100
  • The array is circular: after the last element, searching continues from the beginning, wrapping at most once

arr =

[5, 3, 8, 2]