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.
Community answers
Answer by Coderka14
#include
using namespace std;
class Solution
{
public:
vector next_greater_circular(vector& nums)
{
int n = nums.size();
vector ans(n, -1);
stack st;
for (int i = 0; i < 2 * n; i++)
{
int idx = i % n;
while (!st.empty() && nums[st.top()] < nums[idx])
{
ans[st.top()] = nums[idx];
st.pop();
}
if (i < n)
st.push(idx);
}
return ans;
}
};
Answer by priyanuzkhargharia
def next_greater_circular(nums):
stack=[]
n=len(nums)
answer=[-1]*n
for i in range(2*n):
index=i %n
while stack and nums[index] > nums[stack[-1]]:
answer[stack.pop()] = nums[index]
if i < n:
stack.append(index)
return answer
This is an O (n) time complexity solution. We can also use for loops to solve this question, but then the time complexity will be O (n^2).