Find the first larger value for every element of a circular array
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given an integer array `nums` that is treated as circular: after the last element, scanning continues from the first element. For every index `i`, find the next greater value of `nums[i]`: the first value strictly greater than `nums[i]` met while scanning forward from index `i + 1`, wrapping around past the end, and stopping before returning to index `i`. If no such value exists, the answer for that index is `-1`.
### Function Signature
```python
def next_greater_circular(nums: list[int]) -> list[int]:
```
### Rules
- The scan for index `i` visits indices `i + 1, i + 2, ..., n - 1, 0, 1, ..., i - 1` in that order, so it visits every other index exactly once. For `n = 1` it visits nothing, and the answer is `[-1]`.
- Only a strictly greater value counts; an equal value is skipped.
- Return a list `answer` of length `n`, where `answer[i]` is the value found for index `i`, or `-1` if none is found. Values in `nums` are non-negative, so `-1` cannot be confused with a real value.
### Constraints
- `1 <= n <= 100000`, where `n = len(nums)`
- `0 <= nums[i] <= 10^9`
### Examples
**Example 1**
```text
Input: nums = [3, 8, 4, 1, 2]
Output: [8, -1, 8, 2, 3]
```
For index 2 (value 4), the scan visits 1 and 2, wraps around to 3, and then reaches 8. Nothing exceeds 8, so index 1 gets `-1`. Index 4 (value 2) wraps around and finds 3 immediately.
**Example 2**
```text
Input: nums = [5, 5, 5]
Output: [-1, -1, -1]
```
Equal values do not count as greater.
**Example 3**
```text
Input: nums = [2, 1, 2, 4, 3]
Output: [4, 2, 4, -1, 4]
```
Index 0 skips 1 and the equal value 2 before reaching 4. Index 4 (value 3) wraps around past 2, 1 and 2 to reach 4.
Overview: For every element of an integer array treated as circular, find the first strictly larger value reached by scanning forward and wrapping around, or -1 when none exists. Tests efficient scanning, wrap-around handling and strict comparisons when values repeat.
You are given an integer array `nums` of length `n` that is treated as circular: after the last element, scanning continues from the first element.
For every index `i`, find the next greater value of `nums[i]`: the first value strictly greater than `nums[i]` met while scanning forward starting at index `i + 1`, wrapping around past the end of the array, and stopping before index `i` is reached again. If no such value exists, the answer for index `i` is `-1`.
Implement `next_greater_circular(nums)`, which returns a list `answer` of length `n`, where `answer[i]` is the value found for index `i`, or `-1` if none is found.
### Rules
- The scan for index `i` visits indices `i + 1, i + 2, ..., n - 1, 0, 1, ..., i - 1` in exactly that order, so it visits every other index exactly once. For `n = 1` it visits nothing, and the answer is `[-1]`.
- Only a strictly greater value counts; an equal value is skipped and the scan continues.
- `answer[i]` is the first qualifying value met in that scan order, not necessarily the largest one.
- Values in `nums` are non-negative, so `-1` cannot be confused with a real value.
### Constraints
- `1 <= n <= 100000`, where `n = len(nums)`
- `0 <= nums[i] <= 10^9`
Every input and output value fits in a signed 32-bit integer (none exceeds 2^31 - 1).
### Example 1
```text
Input: nums = [3, 8, 4, 1, 2]
Output: [8, -1, 8, 2, 3]
```
For index 2 (value 4), the scan visits 1 and 2, wraps around to 3, and then reaches 8. Nothing exceeds 8, so index 1 gets `-1`. Index 4 (value 2) wraps around and finds 3 immediately.
### Example 2
```text
Input: nums = [2, 1, 2, 4, 3]
Output: [4, 2, 4, -1, 4]
```
Index 0 skips 1 and the equal value 2 before reaching 4. Index 4 (value 3) wraps around past 2, 1 and 2 to reach 4.
Constraints
- 1 <= n <= 100000, where n = len(nums)
- 0 <= nums[i] <= 10^9
Examples
Input: ([3, 8, 4, 1, 2],)
Expected Output: [8, -1, 8, 2, 3]
Explanation: Source Example 1: index 2 wraps past 1, 2, 3 to reach 8; the maximum 8 gets -1; index 4 wraps to 3.
Input: ([2, 1, 2, 4, 3],)
Expected Output: [4, 2, 4, -1, 4]
Explanation: Source Example 3: index 0 skips 1 and the equal 2 before 4; index 4 wraps past 2, 1, 2 to reach 4.
Hints
- Scanning forward separately from every index can visit up to n - 1 other elements per index; with n up to 100000, look for a way to let a single left-to-right sweep settle the answers of many waiting indices at once.
- The circular scan for index i sees the same elements, in the same order, as a straight scan over the array written twice in a row, starting just after position i.
- Only a strictly greater value ends the search for an index, so equal values never resolve each other and every copy of the largest value ends up with -1.