Finding duplicates in an array is a common interview question. The problem statement can be defined as follows. Given an array of n numbers, give an algorithm for checking whether, there are any duplicates in the array or not? For such questions obvious answer is Brute force or Naive solution.
Solution: Exhaustively search for duplicates in the array. For-each input element, check whether there is any element with the same value. This can be solved with just by using two for loops.
Finding duplicates in an array – Brute Force
/**
* <p>check for array duplicates</p>
* Time Complexity :: O(n^2)
* Space Complexity :: O(1)
* @param a
* @return
*/
public static int checkDuplicatesBruteForce(int[] a){
int n=a.length;
int count=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
count++;
if(a[i]==a[j]&&i!=j){
System.out.println("No.of comparisons BruteForce"+count);
return a[i];
}
}
}
System.out.println("No.of comparisons BruteForce"+count);
return -1;
}In the above solution, we are making an extra comparison, element with it self. We can decrease no.of comparisons by avoiding comparison of element with self.
Finding duplicates in an array -Brute Force with improvement over no.of comparisons
/**
* <p>check for array duplicates</p>
* Time Complexity :: O(n^2)
* Space Complexity :: O(1)
* @param a
* @return
*/
public static int checkDuplicatesBruteForce2(int[] a){
int n=a.length;
int count=0;
for(int i=0;i<n;i++){
for(int j=i;j<n;j++){
count++;
if(a[i]==a[j]&&i!=j){
System.out.println("No.of comparisons BruteForce2"+count);
return a[i];
}
}
}
System.out.println("No.of comparisons BruteForce2"+count);
return -1;
}A sample Test client for above programs
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr1={0,3,2,2,1,5,6,7,9};
int[] arr2={0,3,2,1,5,6,7,9};
/**
* Finding duplicates Brute Force technique
*/
System.out.println(checkDuplicatesBruteForce(arr1));
System.out.println(checkDuplicatesBruteForce(arr2));
/**
* Finding duplicates Brute Force improved technique.
*/
System.out.println(checkDuplicatesBruteForce2(arr1));
System.out.println(checkDuplicatesBruteForce2(arr2));
}Output:
No.of comparisons BruteForce 22
2
No.of comparisons BruteForce 64
-1
No.of comparisons BruteForce2 19
2
No.of comparisons BruteForce2 36
-1