Array Nesting

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:

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

Brainstorm

This is a very interesting problem...the key to this problem is to realize that the set S[K] is basically a loop. Consider the example: S[K] ends when we reach A[2] = 0, and A[0] loops directly back to where we started. So we can remember the starting index of our loop (by setting it to a number that can never be a valid index, say -1), and break the loop whenever we come back to -1. Meanwhile we use a max and curr variable to keep track of the length of the longest S[K] and the length of the current ongoing loop, respectively. At the end of the function we return the max.

As someone pointed out here, this is actually very similar if not the same as DFS. Remembering our starting index is like marking visited nodes, and the loop represents our traversal.

Approach #1: DFS-like Traversal

int arrayNesting(vector<int>& nums) {
    int longest = 0, curr = 1;
    for (int i = 0; i < nums.size(); i++) {
        int j = nums[i];
        nums[i] = -1;
        while (nums[j] != -1) {
            j = nums[j];
            curr++;
        }
        longest = max(longest, curr);
        curr = 1;
    }
    return longest;
}

Time complexity: $$O(n)$$

We perform our calculations in one loop, and each element will only be considered once as a result of our marking of visited integers as negative.

Space complexity: $$O(1)$$