# algorithms – Check if all elements are different

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.