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.