alex1988 alex1988 - 11 days ago 6
C Question

Effeciently check if array has duplicates

There is an array of 1000 elements, all the elements are Normally distributed within a range of 1 - 10000000. How can I check for duplicates faster than

O(n^2)
?

Answer

You can do it in O(max_num + n) time complexity and in O(max_num) space complexity, where max_num is maximum number you can have in your array, using additional array.

You allocate new array countsArr of size 10000001 and initialize all of it's elements to 0. Then you iterate over your primary array, and in every iteration, you add 1 to the new array's element on the index of the number you are currently processing. For example, on first position of your primary array is number 15, so you add 1 to arr[15], etc. After you are done with the iteration, you just iterate over countsArr, and if you find an element, which value is greater than 1, then there are duplicities in your array, otherwise there are not.

EDIT: This is generally faster solution than O(n^2) for large n, but since you have 1000 elements, 1,000^2 = 1,000,000, O(n^2) will be actually faster for n = 1,000 than the solution I proposed.

Comments