##### Welcome to Subscribe On Youtube
• /**

A zero-indexed array A consisting of N different integers is given. The array contains all integers in the range [0, N - 1].

Sets S[K] for 0 <= K < N are defined as follows:

S[K] = { A[K], A[A[K]], A[A[A[K]]], ... }.

Sets S[K] are finite for each K and should NOT contain duplicates.

Write a function that given an array A consisting of N integers, return the size of the largest set S[K] for this array.

Example 1:
Input: A = [5,4,0,3,1,6,2]
Output: 4
Explanation:
A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.

One of the longest S[K]:
S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}
Note:
N is an integer within the range [1, 20,000].
The elements of A are all distinct.
Each element of array A is an integer within the range [0, N-1].

reference: https://leetcode.com/articles/array-nesting/
*/
public class Array_Nesting {

public class Solution_skip_visited {
public int arrayNesting(int[] nums) {
boolean[] visited = new boolean[nums.length];
int res = 0;
for (int i = 0; i < nums.length; i++) {

// @note: if visited, then the count here must be less than previous visit
if (!visited[i]) {
int start = nums[i], count = 0;
do {
start = nums[start];
count++;
visited[start] = true;
}
while (start != nums[i]);
res = Math.max(res, count);
}
}
return res;
}
}

public class Solution_brute_force {
public int arrayNesting(int[] nums) {
int res = 0;
for (int i = 0; i < nums.length; i++) {
int start = nums[i], count = 0;
do {
start = nums[start];
count++;
}
while (start != nums[i]); // if not the initial start number, then continue
res = Math.max(res, count);

}
return res;
}
}

}

############

class Solution {
public int arrayNesting(int[] nums) {
int ans = 0, n = nums.length;
for (int i = 0; i < n; ++i) {
int cnt = 0;
int j = i;
while (nums[j] < n) {
int k = nums[j];
nums[j] = n;
j = k;
++cnt;
}
ans = Math.max(ans, cnt);
}
return ans;
}
}


• // OJ: https://leetcode.com/problems/array-nesting/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int arrayNesting(vector<int>& A) {
int ans = 0;
for (int i = 0; i < A.size(); ++i) {
if (A[i] == -1) continue;
int cnt = 0, j = i;
while (A[j] != -1) {
int k = j;
j = A[j];
A[k] = -1;
++cnt;
}
ans = max(ans, cnt);
}
return ans;
}
};

• class Solution:
def arrayNesting(self, nums: List[int]) -> int:
ans, n = 0, len(nums)
for i in range(n):
cnt = 0
while nums[i] != n:
j = nums[i]
nums[i] = n
i = j
cnt += 1
ans = max(ans, cnt)
return ans

############

class Solution(object):
def arrayNesting(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
cache = [0] * len(nums)
ans = 0
for i, start in enumerate(nums):
if cache[i]:
continue
p = start
length = 1
while nums[p] != start:
cache[nums[p]] = 1
p = nums[p]
length += 1
ans = max(ans, length)
return ans


• func arrayNesting(nums []int) int {
ans, n := 0, len(nums)
for i := range nums {
cnt, j := 0, i
for nums[j] != n {
k := nums[j]
nums[j] = n
j = k
cnt++
}
if ans < cnt {
ans = cnt
}
}
return ans
}

• class Solution {
public int arrayNesting(int[] nums) {
int length = nums.length;
boolean[] visited = new boolean[length];
int maxLength = 0;
for (int i = 0; i < length; i++) {
if (visited[i])
continue;
int curLength = 0;
int index = i;
while (!visited[index]) {
int num = nums[index];
visited[index] = true;
index = num;
curLength++;
}
maxLength = Math.max(maxLength, curLength);
}
return maxLength;
}
}

############

class Solution {
public int arrayNesting(int[] nums) {
int ans = 0, n = nums.length;
for (int i = 0; i < n; ++i) {
int cnt = 0;
int j = i;
while (nums[j] < n) {
int k = nums[j];
nums[j] = n;
j = k;
++cnt;
}
ans = Math.max(ans, cnt);
}
return ans;
}
}


• // OJ: https://leetcode.com/problems/array-nesting/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int arrayNesting(vector<int>& A) {
int ans = 0;
for (int i = 0; i < A.size(); ++i) {
if (A[i] == -1) continue;
int cnt = 0, j = i;
while (A[j] != -1) {
int k = j;
j = A[j];
A[k] = -1;
++cnt;
}
ans = max(ans, cnt);
}
return ans;
}
};

• class Solution:
def arrayNesting(self, nums: List[int]) -> int:
ans, n = 0, len(nums)
for i in range(n):
cnt = 0
while nums[i] != n:
j = nums[i]
nums[i] = n
i = j
cnt += 1
ans = max(ans, cnt)
return ans

############

class Solution(object):
def arrayNesting(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
cache = [0] * len(nums)
ans = 0
for i, start in enumerate(nums):
if cache[i]:
continue
p = start
length = 1
while nums[p] != start:
cache[nums[p]] = 1
p = nums[p]
length += 1
ans = max(ans, length)
return ans


• func arrayNesting(nums []int) int {
ans, n := 0, len(nums)
for i := range nums {
cnt, j := 0, i
for nums[j] != n {
k := nums[j]
nums[j] = n
j = k
cnt++
}
if ans < cnt {
ans = cnt
}
}
return ans
}