alex1988 alex1988 - 6 months ago 29
C Question

Efficiently 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



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.

EDIT2: As Eugene Sh. pointed out, there is actually no need to iterate over the aditional array, as you can immediatelly say, that the array has duplicities, when you increment an index, which already holds 1. When you do, you can say that there is at least one duplicity and terminate. This improvement makes the algorithm have O(n) time complexity in the worst case (no duplicities).