Finding duplicates in an array using Hashtables -O(n)

by

We have seen the Brute force and sorted array solutions for the problem statement, Now to even minimize the time complexity of finding duplicates we’ll introduce hashing techniques so that, the problem statement can take only O(n) time. We’ll conditionally add input array elements to HashMap. We’ll check for the input array element that we are going to add into HashMap whether it is available in the map or not, if it is not available we’ll add element as key and value as zero. If it is available in the map then increment the value by 1 for the respective keys. Here is the technique for finding duplicates in an array using hashtables.

Finding duplicates in a array using Hashtables -O(n)

/**
 * <p>Check for duplicates in the array with Hashing</p>
 * Time Complexity  ::O(n) 
 * Space Complexity ::O(n) 
 * @param a
 * @return
 */
public static int checkDuplicatesWithHashMap(int[] a){
int n=a.length;
Map<Integer,Integer> map=new HashMap<Integer,Integer>();
for(int i=0;i<n;i++){
   if(map.containsKey(a[i])){
	int value=(int)((Integer)map.get(a[i]));
	value=value+1;
	map.put(a[i],value);
	return a[i];
   }else{
	map.put(a[i],0);
   }
}
return -1;
}

 Finding duplicates using List and Hashset in Java

/**
 * <p>Check duplicates by making list and set comparing length of lists</p>
 * @param a
 * @return
 */
public static boolean checkDuplicateUsingSet(int[] a){
List inputList = Arrays.asList(a);
Set inputSet = new HashSet(inputList);
if(inputSet.size()< inputList.size()){
    return true;
}
return false;
}

Sample Test Client for the 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};
/**
 * Checking duplicates in the array using Hashing
 * Hashing takes O(1) constant time for searching element in hashtable in   * avg case and in worst case it takes O(n) time
 * For looping through n elements and adding to HashMap takes O(n) time
 * Time Complexity  ::O(n)
 * Space Complexity ::O(n)  As we are storing elements into HashMap, which  * is an extra space.
*/
	int[] arr4={0,3,2,2,1,5,6,7,9};
	System.out.println(checkDuplicatesWithHashMap(arr4));

/**
 * Check duplicates using list and set
 */

 System.out.println(checkDuplicateUsingSet(arr1));
}

Leave a Comment