Counting a cycle

Question

An interview question I got -

Each element of an int array points to the another element, eventually creating a cycle. Starting at array[0], find the length of the cycle.

Examples:

Input:

array = [1, 0]

Output:

2

Input:

array = [1, 2, 1]

Output:

2

Note how element 3 is not part of the cycle

Input:

array = [1, 3, 0, 4, 1]

Output:

3

Note how element 0 is used to find the cycle, but is not part of the cycle count.

Constraints:

• Must be in Java 7
• Elements will always be positive or 0 and never point outside the array
• Elements will never point to themselves
• There will always be a cycle
• The cycle will be at least length 2

My Code:

import java.util.HashMap;
import java.util.Map;

//Time Complexity: O(n) (worst case)
//Space Complexity: O(n) (worst case)
class CycleDetector{
    private Map<Integer, Integer> visitedElements = new HashMap<Integer, Integer>();
    private int counter = 0;

    public int countCycle(int[] array){
        int startOfLoop = visitNextElement(array, array[0]);
        return counter - startOfLoop;
    }

    private int visitNextElement(int[] array, int e){
        counter++;

        Integer startOfLoop = visitedElements.put(e, counter);
        if(startOfLoop == null){
            return visitNextElement(array, array[e]);
        }
        else{
            return startOfLoop;
        }
    }
}

I also had an alternative idea where instead of have a Map<int int> I would just have a Set<int>. In this case when I found the cycle I would just go back to the start of the cycle and re-run it (but this time with a counter). This would trade speed for memory, but both would still technically be O(n). I ultimately decided against this because if you scale this up to arrays that are not of ints, the solution I wrote would do better (since the extra memory is ints, where as the extra computations could be complex).

Answer 1

Your code is neat, and it is easy to follow the logic through.

On the other hand, I am confused by two things.

1. Your class needs to be instantiated, but it is not reusable. After calling countCycles(...) the instance is 'burned'. Why don't you use static methods, or create an instance for each run?

2. The data structure you use for storing the path taken so far is relatively expensive. I would have used a parallel int-array for that. As you loop through the data you add the count to the parallel array at the matching index.

So, I would have written:

public static int countCycles(int[] data) {
    int[] counters = new int[data.length];
    int index = 0;
    int count = 0;
    while(counters[index] == 0) {
        counters[index] = count++;
        index = data[index];
    }
    return count - counters[index];
}

That essentially does the same task as yours, but uses an array instead of a Map, and it thus removes all the autoboxing and other overhead.

The drawback here is that it always uses the worst-case \$O(n)\$ space (even though that is likely significantly less than the average case for the HashMap in terms of absolute space. Each entry in the HashMap is about 96 bytes or more, whereas the array above is simply 4 bytes per entry.

This got me thinking, and i realized we can do the whole thing in \$O(n)\$ time, and \$O(1)\$ space if you can reuse the space that's given as input. If you store the count as a negative value, then you can put that in to the input array, and not allocate any other space:

public static int countCyclesBurn(int[] data) {
    int index = 0;
    int count = 0;
    while(data[index] >= 0) {
        int tmp = data[index];
        data[index] = -(++count);
        index = tmp;
    }
    return count + data[index] + 1;
}

The above will overwrite the relevant cells in the data array with the count at that time. This will be the fastest system, but comes at the expense of corrupting the input data. If that is permitted, then that's fine.

Answer 2

It is a classic problem; it can be done in constant space and linear time. First, find an element belonging to the loop:

find_loop
    slow = 0
    fast = 0
    do
       slow = next(slow)
       fast = next(fast)
       fast = next(fast)
    while slow != fast
    return slow

The index returned belongs to the loop. Now you may find the loop length:

count_loop_length(index)
    length = 0
    cursor = index
    do
        cursor = next(cursor)
        length += 1
    while cursor != index
    return length