Suppose we have $ n $ double elements $ a_1 dots a_n $ . We want to know if two of the elements of the array are identical. And we have a hash function $ h $ which assigns each double value an integer between $ 1 $ and $ n $. Let $ m: = {(i, j): a_j neq a_i text {and} h (a_j) = h (a_i) } $

How can I check if all $ n $ the elements are different $ O (n + | m |) $ time and $ O (n) $ memory. $ h (x) $ can be calculated in $ O (1) $)

1) The naiv approach would be to check for all $ n $ elements if there is another element with the same value that requires $ O (n ^ 2) $ time.

2) A better solution would be to sort the necessary elements $ O (n cdot log (n)) $ time and then look for each item so in total it would be $ O (n cdot log (n)) $.

But I do not know how can I solve this problem faster. I think that the approach 1) or 2) can not be further improved. Apparently, I have to use the hash function in one way or another, but I do not see how.