## Find the duplicates in an array in O(n) time

There is actually no algorithm to give perfect O(n) time for processing.

~~However, there is a way to find the solution in worst case scenario of O(2n) i.e O(n).~~

**ke’s** comment about the complexity being O(n^{2}) is indeed correct.

You can read more about it at Stackoverflow.com post.

I present the solution below in JavaScript and Java.

It is a simple solution based on Associative Arrays in JavaScript and Hash Maps in Java.

In each case you store the elements of input array into a hash based datastructure.

This ensures that you do not repeat the same element and can count the number of instances of duplicate elements.

**JavaScript solution**

//find the duplicates in an array in O(n) function findDupsInArray() { var arr = new Array("1","1","2","3","1","3","4","4","5","5","5","5","23","55","23"); var assArr = new Array(); for(i=0;i<arr.length;i++) { if(arr[i] in assArr) { assArr[arr[i]] = assArr[arr[i]]+1; } else { assArr[arr[i]] = 1; } } for(var key in assArr) { alert(key + ' = ' + assArr[key]); } } findDupsInArray();

**Java Solution**

package algorithms; import java.util.Map; import java.util.HashMap; /** * * @author amitrai */ public class FindDuplicatesInArray { public static void main(String[] args) { String[] arr = {"1","1","2","3","1","3","4","4","5","5","5","5","23","55","23"}; Map dataMap = new HashMap(); for(int i=0;i<arr.length;i++) { if(dataMap.containsKey(arr[i])) { dataMap.put(arr[i], dataMap.get(arr[i])+1); } else { dataMap.put(arr[i], 1); } } for(String key : dataMap.keySet()) { System.out.println(key+"="+dataMap.get(key)); } } }

Advertisements

Not correct. First, there is no difference between O(n) and O(2n). Second, containsKey itself has O(n) worst case time so you get O(n²) overall.

Credits: Thanks to D. and Y. for confirming my hunch on this.

Thanks ke, point well taken.