390. Next Greater Element II
You are given a circular array of integers nums — after the last element, the walk wraps back to the front.
For every index i, find the value of the first element that is strictly greater than nums[i] when walking forward from i (wrapping around if needed, but never looking at nums[i] itself twice). If no such element exists anywhere in the circle, that position's answer is -1.
Return the array of answers, one per input position, in the same order as nums.
Example 1:
Input: nums = [1, 2, 1]
Output: [2, -1, 2]
Explanation: From the first 1 the next value forward is 2. The 2 is the maximum of the circle, so nothing beats it: -1. The last 1 wraps around and also reaches the 2.
Example 2:
Input: nums = [1, 2, 3, 4, 3]
Output: [2, 3, 4, -1, 4]
Explanation: Each of 1, 2, 3 is beaten by its immediate neighbor. The 4 has no greater element anywhere. The trailing 3 wraps past 1 and 2 and is finally beaten by the 4.
Constraints:
- 1 ≤ nums.length ≤ 10⁴
- -10⁹ ≤ nums[i] ≤ 10⁹
- "Greater" is strict — an equal value does not count.
Hints:
Brute force works: from each index walk forward at most n − 1 steps using `(i + j) % n` and stop at the first strictly greater value. That's O(n²).
For the linear solution, keep a stack of indices whose answer is still unknown; their values sit in decreasing order. When a new value arrives, it resolves every smaller value on top of the stack. Run the sweep for two laps (`i` from 0 to 2n − 1, reading `nums[i % n]`) so wrapped answers get resolved — but only push indices during the first lap.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [1, 2, 1]
Expected output: [2, -1, 2]