# Array Nesting

# You are given an integer array nums of length n where nums is a permutation of the numbers in the range [0, n - 1].
# You should build a set s[k] = {nums[k], nums[nums[k]], nums[nums[nums[k]]], ... } subjected to the following rule:
#     The first element in s[k] starts with the selection of the element nums[k] of index = k.
#     The next element in s[k] should be nums[nums[k]], and then nums[nums[nums[k]]], and so on.
#     We stop adding right before a duplicate element occurs in s[k].
# Return the longest length of a set s[k].

# Example 1:

# Input: nums = [5,4,0,3,1,6,2]
# Output: 4
# Explanation: 
# nums[0] = 5, nums[1] = 4, nums[2] = 0, nums[3] = 3, nums[4] = 1, nums[5] = 6, nums[6] = 2.
# One of the longest sets s[k]:
# s[0] = {nums[0], nums[5], nums[6], nums[2]} = {5, 6, 2, 0}

class Solution:
    def arrayNesting(self, nums):
        maximum = 0
        for i, num in enumerate(nums):
            if num < 0: continue
            idx, cnt = num, 0
            while nums[idx] >= 0:
                cnt, nums[idx], idx = cnt+1, -1, nums[idx]
            else:    
                maximum = max(maximum, cnt)
        return maximum

        
if __name__ == '__main__':
    sol = Solution()
    nums = [5,4,0,3,1,6,2]
    print(sol.arrayNesting(nums))

""" 
class Solution {
    public int arrayNesting(int[] nums) {
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            max = Math.max(search(nums, i), max);
        }
        return max;
    }
    
    private int search(int[] nums, int idx) {
        int size = 0;
        while (true) {
            if (nums[idx] == idx) return 1; // don't forget this!! self-point element
            if (nums[idx] < 0) break;
            size += 1;
            nums[idx] *= -1;
            idx = Math.abs(nums[idx]);
        }
        return size;
    }
}
"""