45. Next Greater Element — Circular Array
From each position, walk forward through the array, wrapping from the end to the beginning at most once. Find the first encountered value that is strictly larger than the starting value.
Do not return the largest value anywhere in the array unless it is also the first qualifying value. Equal values do not satisfy the strict comparison.
Example 1
Input
[1,2,1]
Output
[2,-1,2]
Explanation: The last one wraps to the two at index one.
Example 2
Input
[-2,-1]
Output
[-1,-1]
Explanation: The first -1 is an actual greater value; the second is absence under the same value-only representation.
Constraints
0 <= nums.length <= 105-231 <= nums[i] <= 231 - 1
Hints
Hint 1
What work can one larger incoming value finish for earlier positions?
Hint 2
How can the head of the array serve tail queries without copying the input?
Hint 3
Scan 2n virtual positions and push indices only in the first pass.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Wraparound resolves the tail
[1,2,1]
[2,-1,2]