565. Array Nesting -----------M

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:

1. N is an integer within the range [1, 20,000].
2. The elements of A are all distinct.
3. Each element of A is an integer within the range [0, N-1].

 A:

关键在于， 会形成一个个彼此独立的circle,

Approach #2 Using Visited Array [Accepted]

Algorithm

In the last approach, we observed that in the worst case, all the elements of the $nums$ array are added to the sets corresponding to all the starting indices. But, all these sets correspond to the same set of elements only, leading to redundant calculations.

We consider a simple example and see how this problem can be resolved. From the figure below, we can see that the elements in the current nesting shown by arrows form a cycle. Thus, the same elements will be added to the current set irrespective of the first element chosen to be added to the set out of these marked elements.

Thus, when we add an element $nums[j]$ to a set corresponding to any of the indices, we mark its position as visited in a $visited$ array. This is done so that whenever this index is chosen as the starting index in the future, we do not go for redundant $count$ calculations, since we've already considered the elements linked with this index, which will be added to a new(duplicate) set.

By doing so, we ensure that the duplicate sets aren't considered again and again.

Further, we can also observe that no two elements at indices $i$ and $j$ will lead to a jump to the same index $k$, since it would require $nums[i] = nums[j] = k$, which isn't possible since all the elements are distinct. Also, because of the same reasoning, no element outside any cycle could lead to an element inside the cycle. Because of this, the use of $visited$ array goes correctly.

class Solution {
public:
    int arrayNesting(vector<int>& nums) {
        int N = nums.size();
        vector<bool> V(N,false); // vector of whether visited
        
        int maxLen = -1;
        for(int i =0;i<N;i++){
            int seed = i;
            if(V[seed]) // if already visited
                continue;
            int count = 0;
            while(not V[seed]){
                V[seed] = true;
                count++;
                seed = nums[seed];
            }
            maxLen = max(maxLen ,count);
        }
        return maxLen;
    }
};