Java code with an example to illustrate


  • 0
    A
    public class Solution {
        public int arrayNesting(int[] nums) {
            // algorithm 2017/06/15: It is easy to translate this problem into splitting all given numbers into a number of 'islands'/sets. For numbers in each set, they are cycled based on A[K], A[A[K]], A[A[A[K]]], ... 
            // Example 
        /*
                  2 4 5 3 0 1 => two sets (2,5,1,4,0) and (3)
            S[0]: 2 5 1 4 0
            S[1]: 4 0 2 5 1
            S[2]: 5 1 4 0 2
            S[3]: 3
            S[4]: 0 2 5 1 4
            S[5]: 5 1 4 0 2
        */
            // we will need to find the island with most numbers
    
            if (null == nums || 0 == nums.length) {
                return 0;
            }
    
            boolean[] visited = new boolean[nums.length];
            int maxSetSize  = 0;
    
            for (int startK = 0; startK < nums.length; startK++) {
                if (visited[startK]) {
                    continue;       // the number is already put into certain set before, skip it
                }
    
                // now let us start a new set
                visited[startK]  = true;
                Set<Integer> set = new HashSet<>();
                int chainedNum   = nums[startK];
                do {
                    if (!set.add(chainedNum)) {
                        break;
                    } else {
                        visited[chainedNum] = true;
                    }
                    chainedNum = nums[chainedNum];
                } while (true);
                maxSetSize = Math.max(maxSetSize, set.size());
            }
            return maxSetSize;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.