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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
/** * <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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
/** * <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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
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:
|
1 2 3 4 5 6 7 8 |
No.of comparisons BruteForce 22 2 No.of comparisons BruteForce 64 -1 No.of comparisons BruteForce2 19 2 No.of comparisons BruteForce2 36 -1 |