Find the next greater value for each element in a circular array.
Given a circular array of integers, determine for every position the first value to its right that is strictly greater than the current value. Because the array is circular, after the last element you continue scanning from the beginning as needed. If no greater value exists for an element, return -1 for that position.
A value is considered the next greater element for an index if it appears later in the circular traversal and is the first element encountered with a larger value.
Input Format
- An integer array
numsof lengthn. - The array is treated as circular.
Return an array ans of length n, where ans[i] is the next greater element for nums[i], or -1 if none exists.
Output Format
- Return an integer array
ansof the same length asnums. ans[i]should contain the first strictly larger value encountered while scanning circularly to the right from indexi.- If no such value exists, set
ans[i] = -1.
Constraints
1 <= n- The array may contain duplicate values.
- The answer for each position must be based on a circular rightward scan.
- Values can be negative or positive integers.
Example 1
Input
nums = [1, 2, 1]
Output
[2, -1, 2]
Explanation
- For
1at index 0, the next greater value to the right is2. - For
2, there is no greater value in the circular scan. - For
1at index 2, wrap around and find2.
Example 2
Input
nums = [3, 8, 4, 1, 2]
Output
[8, -1, 8, 2, 3]
Explanation
Scanning circularly:
3 -> 88 -> -14 -> 81 -> 22 -> 3
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.