Duplicates in the array can be found by general Brute force solution in the O(n^2) time. Can there be any solution that would take less time than the Brute force solution? Yes. obviously, by sorting the array input. For any problem statement, for improving the time complexity check whether sorting on input will work.If you use Quick sort or Merge sort for sorting the array, it will take O(nlogn) time, and for checking duplicates, it will take O(n) time. On the whole asymptotically, it is , O(nlogn) time.
Finding duplicates in a sorted array – O(nlogn)
/**
* <p>Checking duplicates in an array by sorting</p>
* Time Complexity ::O(nlogn)
* Space Complexity ::O(1)
* @param a
* @return
*/
public static int checkDuplicatesWithArraySorted(int[] a){
int n=a.length;
//Sort array in place O(nlogn)
//for checking duplicate O(n)
for(int i=0;i<n-1;i++){
if(a[i]==a[i+1])
return a[i];
}
return -1;
}Sample Test client for above program
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};
/**
* Checking duplicates in the array by sorting
* Sorting in place takes O(nlogn) time and after sorting, for checking duplicates takesO(n)
* Time Complexity ::O(nlogn)
* Space Complexity ::O(1)
*/
//we are directly taking sorting array.
int[] arr3={0,1,2,2,5,6,7,9};
System.out.println(checkDuplicatesWithArraySorted(arr3));
}