fastest way to find if all the elements of an array are distinct?

Question

I am looking for a faster way to find whether an array of elements contains distinct elements only. The worst thing to do is to take each element and compare it to every other element in the array. Next best would be to sort the list and then compare, which still does not improves this much. Is there any other way to do this?

Answer 1

Brute-force:

Brute-force (checking every element with every other element) takes O(n2).

Sorting:

Sorting takes O(n log n), which is generally considered to be a fairly decent running time.

Sorting has the advantage above the below (hash table) approach in that it can be done in-place (O(1) extra space), where-as the below takes O(n) extra space.

Hash table:

An alternative is to use a hash table.

For each item:

• Check if that item exists in the hash table (if it does, all items are not distinct) and
• Insert that item into the hash table

Since insert and contains queries run in expected O(1) on a hash table, the overall running time would be expected O(n), and, as mentioned above, O(n) extra space.

Bit array:

Another alternative, if the elements are all integers in some given range, is to have a bit array with size equal to the range of integers.

Similarly to what was done for the hash table approach, for each element, you'd check whether the applicable bit is set, and then set it.

This takes O(m + n) time and O(m) extra space where m is the range of integers and n is the size of the array (unless you consider allocating the array to be free, in which case it just takes O(n) time).