alex1988 - 1 year ago 101
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

`O(n^2)`
?

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).