I had an interview today which involved this very question and in order to widen my algorithmic knowledge. I am trying to see if there are any better suggestions.

I was trying to find duplicates in an array without using java.util and widen my algorithmical knowledge in regards to addressing space and time complexities.

Below is the code I produced during the technical assessment:

public static boolean isThereDuplicates(int[] A){
for (int i = 0; i < A.length; i++)
for (int j = i + 1; j < A.length; j++){
if (A[i] == A[j])
return true;
}
return false;
}

This simple algorithm looks identical to the Bubble Sort, which runs in O(N^2). Is there any other better algorithms that I could use to achieve this?

## Answer

If the values of A are reasonably bounded (i.e. you have enough RAM) you could use the bones of the radix-sort algorithm to find a duplicate in O(n).

public static boolean containsDuplicates(int[] A)
{
// Create a zero-initialised array the size of the maximum allowed value in A.
int[] count = new int[maximumValuePossible(A)];
for (int i = 0; i < A.length; i++)
{
if (count[A[i]] != 0)
{
// The value at A[i] is already in the histogram -> duplicate!
return true;
}
// A[i] is not in the histogram yet.
count[A[i]]++;
}
return false;
}

Edit: To return a copy of the array with duplicates removed you could then do:

public static int[] stripped(int[] A)
{
int[] count = new int[maximumValuePossible(A)];
int uniques = 0;
for (int i = 0; i < A.length; i++)
{
count[A[i]]++;
if (count[A[i]] == 1)
{
uniques++;
}
}
if (uniques == 0) return null;
int[] retArray = new int[uniques];
int retIndex = 0;
for (int i = 0; i < count.length; i++)
{
if (count[i] > 0)
{
retArray[retIndex++] = count[i];
}
}
return retArray;
}

## Recent Comments