An interview question I got -
Each element of an
int
array points to the another element, eventually creating a cycle. Starting atarray[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 int
s, the solution I wrote would do better (since the extra memory is ints, where as the extra computations could be complex).