Determining the cardinality of sets defined by recursively following indexes

Question

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.

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<Integer> resultSet = null;

         if(arrayLength <= 0)
         return 0;

         for(int i = 0; i < arrayLength; i++) {
           Set<Integer> tempSet = new LinkedHashSet<Integer>();
           int tempNum = A[i];
           count = 0;
           while(!tempSet.contains(tempNum)){
               tempSet.add(tempNum);
               tempNum = A[tempNum];
               count++;
           }
           if(count > 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)?

Answer 1

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<Integer> visited = new HashSet<Integer>();

     if(arrayLength <= 0)
     return 0;

     for(int i = 0; i < 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 > maxsize) { 
          maxsize = count;
       }
    }
     return maxsize;
 }

Answer 2

Remove unused elements

         Set<Integer> resultSet = null;

You don't actually read this at any time. So you can delete this line and

              resultSet = tempSet;

without any change in functionality.

Indentation

         if(arrayLength <= 0)
         return 0;

This is difficult to read. Because you put both statements at the same level of indentation, the natural reading is that you always return here. But this is actually a conditional return.

This would be more readable as

         if (arrayLength <= 0)
             return 0;

But many would actually write it as

         if (arrayLength <= 0) return 0;

Then there's no confusion about whether the return is conditional or not.

I would actually prefer to always use the block form.

         if (A.length <= 0) {
             return 0;
         }

This way we expect that what starts with an if will end with a }. Always the same behavior rather than an individual behavior for each.

There are also certain kinds of editing errors that the block form makes less likely.

Also, your indentation is all over the place. Sometimes you indent four spaces. Other times, you indent two or three spaces. You should pick one and stick to it. The Java standard is four spaces, but the most important thing is to be consistent in your program.

Know your interface

           while(!tempSet.contains(tempNum)){
               tempSet.add(tempNum);

You can get the identical effect with

           while (tempSet.add(tempNum)) {

The add method calls contains or its equivalent and immediately returns false if contains would return true.

Use your interface

           if(count > maxsize) { 
              maxsize = count;

Set includes a size() which returns the same information as you track in count. So you can just say

           if (tempSet.size() > maxsize) { 
               maxsize = tempSet.size();

Then we can get rid of count altogether.

Iterate with for loops

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

Functionally it doesn't matter, but it's often easier to read a for loop than a while loop.

           for (int j = i; tempSet.add(j); j = A[j]) ;

Now we can easily see that we are iterating j until we encounter a node that we've already seen.

I started the cycle at i rather than A[i] to simplify things.

Optimization

You are calculating the cycle length separately for each cycle. This means that the worst case performance occurs for arrays of the form { 1, 2, 3, 0 }, where the cycle includes the entire set. That gives a quadratic worst case time. The best case is linear, e.g. for { 0, 1, 2 }, where each element points to itself.

Given the problem space, you don't need a Set. You could use an array instead. This will work because the indexes and the values are from the same space and both unique. So every index is present as exactly one value. Each and every element is part of some cycle and only one cycle. Of course, if you use an array then count is necessary again.

        boolean[] visited = new boolean[A.length];
        int maxSize = 0;

        for (int i = 0; i < A.length; i++) {
            int count = 0;
            for (int j = i; !visited[j]; j = A[j]) {
                visited[j] = true;
                count++;
            }

            if (count > maxSize) { 
                maxSize = count;
            }
        }

        return maxSize;

This returns the same result, but it will run in linear time, even in the worst case. The difference is that it only visits each element of the cycle twice. This is because once the inner loop marks something as visited, the inner loop will no longer process that item.

The original would visit each element of the cycle R times, where R is the number of elements in the cycle. In the worst case, R equals N, the number of elements in the input.

The name visited is clearer about what the variable holds than tempSet.

By declaring visited outside the loop, it keeps us from forgetting what we have already learned.