Array Nesting

Problem

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].

Solution

Visited Array Solution: O(n) time, O(n) space

public class Solution {
    public int arrayNesting(int[] nums) {
        int res = 0;
        boolean[] visited = new boolean[nums.length];
        for (int num : nums) {
            int count = 0;
            while (!visited[num]) {
                count++;
                visited[num] = true;
                num = nums[num];
            }
            res = Math.max(res, count);
        }
        return res;
    }
}

Mark Negative Solution: O(n) time, O(1) space

public class Solution {
    public int arrayNesting(int[] nums) {
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < 0) continue;
            int count = 1, next = nums[i]; //i is the current, hence nums[i] is the next 
            nums[i] *= -1;
            while (i != Math.abs(next)) {
                count++;
                nums[Math.abs(next)] *= -1;
                next = nums[Math.abs(next)];
            }
            res = Math.max(res, count);
        }
        return res;
    }
}

Analysis

This problem is essentially about finding longest circle from the given array
Because it has n elements, the cycles won't be overlapped
That is to say, we don't have to worry about counting elements after we marked it visited
We use Mark Negative to mark visited element in order to save space
Notice that the time complexity is O(n) even there are nested loops
This is because each element will be visited at most once