Determining the cardinality of sets defined by recursively following indexes 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 &lt; N are defined as follows:
  
  S[K] = { A[K], A[A[K]], A[A[A[K]]], ... }.
  
  Sets S[K] are finite for each K.
  
  Write a function that, given an array A consisting of N integers,
  returns the size of the largest set S[K] for any array input.


This is my solution :

    public int solution(int[] A) {

         int arrayLength = A.length;
         int maxsize = 0;
         int count = 0;
         Set&lt;Integer&gt; resultSet = null;

         if(arrayLength &lt;= 0)
         return 0;

         for(int i = 0; i &lt; arrayLength; i++) {
           Set&lt;Integer&gt; tempSet = new LinkedHashSet&lt;Integer&gt;();
           int tempNum = A[i];
           count = 0;
           while(!tempSet.contains(tempNum)){
               tempSet.add(tempNum);
               tempNum = A[tempNum];
               count++;
           }
           if(count &gt; maxsize) { 
              maxsize = count;
              resultSet = tempSet;
           }
        }
         return maxsize;
     }


For example, given array A such that:

  A[0] = 5    A[1] = 4    A[2] = 0
  A[3] = 3    A[4] = 1    A[5] = 6
  A[6] = 2


the function should return 4, because set S[2] equals { 0, 5, 6, 2 } and has four elements. No other set S[K] has more than four elements.

My solution normally works but gives TIMEOUT ERROR for large sizes. How can I optimize the complexity of this code from O(N*R) to O(N)?
You are visiting every node to check their chain, but if they've already been visited by a previous chain they don't need to be checked again.

So you can have a single "visited" HashSet outside the main loop which can be used to check whether they have been visited in the outside loop and used to break the inside loop. 

Then in each of the outside loop iterations you can continue if you have previously visited.

Note also that you don't need to return and store the actual cycle, just the length.

public int solution(Integer[] A) {

     int arrayLength = A.Length;
     int maxsize = 0;
     int count = 0;
     Set&lt;Integer&gt; visited = new HashSet&lt;Integer&gt;();

     if(arrayLength &lt;= 0)
     return 0;

     for(int i = 0; i &lt; arrayLength; i++) {
       if(visited.contains(i))
            continue;

       int tempNum = A[i];
       count = 0;
       while(!visited.contains(tempNum)){
           visited.add(tempNum);
           tempNum = A[tempNum];
           count++;
       }

       if(count &gt; maxsize) { 
          maxsize = count;
       }
    }
     return maxsize;
 }