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; }