A zero-indexed array A of length N contains all integers from 0 to N-1. Find and return the longest length of set S, where S[i] = {A[i], A[A[i]], A[A[A[i]]], ... } subjected to the rule below.

Suppose the first element in S starts with the selection of element A[i] of index = i, the next element in S should be A[A[i]], and then A[A[A[i]]]… By that analogy, we stop adding right before a duplicate element occurs in S.

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 A is an integer within the range [0, N-1].

Difficulty: interview

Starter code:

class Solution:
    def arrayNesting(self, nums: List[int]) -> int:
        

Solutions:
class Solution:
     def arrayNesting(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         best = 0
         n = len(nums)
         p = []
         for i in range(len(nums)):
             j = i
             current = 0
             while nums[j] != -1:
                 current += 1
                 n -= 1
                 k = j
                 j = nums[j]
                 nums[k] = -1
             best = max(best,current)
             if n <= best:
                 return best
         return best


class Solution:
     def arrayNesting(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         maxlen = 0
         for i in range(0,len(nums)):
             cur = nums[i]
             if(cur >=0):
                 curlen = 0
                 nums[i] = -1
                 while cur>=0:
                     j = cur
                     cur = nums[j]
                     nums[j] = -1
                     curlen = curlen+1
                 if curlen>maxlen:
                     maxlen=curlen
         return maxlen


class Solution:
     def arrayNesting(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
 
         
         dic = set()
         ma = 0
         for i in nums:
             if i not in dic: # not considered
                 set_ = set()
                 while i  not in set_:
                     set_.add(i)
                     i = nums[i]
                 ma = max(ma,len(set_))
                 dic.update(set_)
         return ma

class Solution:
     def arrayNesting(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         ans, step, n = 0, 0, len(nums)
         signal = [False] * n
         for i in range(n):
             while not signal[i]:
                 signal[i] = True
                 step += 1
                 i = nums[i]
                 ans = max(ans, step)
             step = 0
         return ans

class Solution:
     def arrayNesting(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         longest = 1
         for i in range(len(nums)):
             count = 1
             if i==nums[i]:
                 continue
             index = nums[i]
             nums[i] *= -1
             flag = True
             while flag:
                 if index<0:
                     flag = False
                     continue
                 if nums[index]==0:
                     count += 1
                     tmp = index
                     index = nums[index]
                     nums[tmp] = -20001
                 if nums[index]>0:
                     count += 1
                     tmp = index
                     index = nums[index]
                     nums[tmp] *= -1
                 else:
                     if count>longest:
                         longest = count
                     flag = False
         return longest

class Solution:
     def arrayNesting(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         maxLength = 0
         for i in range(len(nums)):
             length = 0
             j = i
             while nums[j] >= 0:
                 length += 1
                 tmp = nums[j]
                 nums[j] = -1
                 j = tmp
             maxLength = max(maxLength, length)
         return maxLength

class Solution:
     def arrayNesting(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         curr = 0
         maxLen = 0
         tovisit = set([i for i in range(len(nums))])
         while len(tovisit) > 0:
             p = tovisit.pop()
             curr = 1
             while nums[p] != -1 and nums[p] in tovisit:
                 tovisit.remove(nums[p])
                 nums[p], p = -1, nums[p]
                 curr += 1
             maxLen = max(maxLen, curr)
         return maxLen