The problem is about finding the largest cycle in a permutation array. Since each number is unique and in the range [0, n-1], following the chain from any index will eventually loop back, forming a cycle. By marking visited elements, we avoid redundant work and ensure each cycle is counted only once.
classSolution {
public:int arrayNesting(vector<int>& nums) {
int n = nums.size(), ans =0;
vector<bool> vis(n, false);
for (int i =0; i < n; ++i) {
if (!vis[i]) {
int cnt =0, j = i;
while (!vis[j]) {
vis[j] = true;
j = nums[j];
++cnt;
}
ans = max(ans, cnt);
}
}
return ans;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
classSolution {
publicintarrayNesting(int[] nums) {
int n = nums.length, ans = 0;
boolean[] vis =newboolean[n];
for (int i = 0; i < n; ++i) {
if (!vis[i]) {
int cnt = 0, j = i;
while (!vis[j]) {
vis[j]=true;
j = nums[j];
cnt++;
}
ans = Math.max(ans, cnt);
}
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
classSolution:
defarrayNesting(self, nums: list[int]) -> int:
n: int = len(nums)
vis: list[bool] = [False] * n
ans: int =0for i in range(n):
ifnot vis[i]:
cnt: int =0 j: int = i
whilenot vis[j]:
vis[j] =True j = nums[j]
cnt +=1 ans = max(ans, cnt)
return ans