Does array have a unique element?

Question

I am looking for the most efficient algorithm to check if an array has a unique element in it. The result need not be the unique element, just true or false accordingly. I know I can reach O(n) efficiency with a hash table or somesuch, but I am still looking for a result which is more efficient space-wise, too.

e- the array is unsorted, and contains integers.

Answer 1

If the number of possible values is small and known in advance, you could use a bit array (which would be O(n) in time, O(n) in space, and would require less space than a hash table).

If the number of possible values is large, and you need this to be deterministic, then you could either use a hash table (which is O(n) if you have a good hash function and if you don't need to grow the hash table) or sort the list in place (which is O(n*lg(n) to sort, plus O(n) to search for the first unique element)

If the number of possible values is large, you do not need this to be deterministic, and if you want to see if a specific element is in the set, you could also use a Bloom Filter. A Bloom Filter is more space-efficient than a hash map, but there is a probability of false positives (the data structure thinks an element is in the set when it isn't)