alex1988 - 1 year ago 73
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)`
?

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.