Check whether all elements are different

Question

Assume we have $n$ double elements $a_1 \dots a_n$. We want to find out if two of the elements of the array are identical. And we have a hash function $h(x)$ which assigns each double value an integer between $1$ and $n$ and which can be calculate in $O(1)$ time. Let $m := \{(i,j) : a_j \neq a_i \text{ and } h(a_j) = h(a_i)\}.$

How can i check if all $n$ elements are different in $O(n+ |m|)$ time and $O(n)$ memory?

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

2) A better way would be if i sort the elements, which needs $O(n \cdot \log(n))$ time and then check each adjacent pair of elements. In total it would be $O(n \cdot \log(n))$.

But i don't know how i can solve this problem quicker. I think neither approach 1) nor 2) can be further improved. Apparently I have to use the hash function somehow, but I don't see how.

Answer 1

This sounds like an assignment, so I'll just give you a few things to think about:

• Using a hash table/hash map allows you to access elements in near $O(1)$ time. The only reason it's not exactly $O(1)$ is because of the collisions, $m$.
• Given two elements $a_i$ and $a_j$, if $h(a_i) = h(a_j)$, the two elements may or may not be equal. The hash table has to handle this collision in some way; you may then have to go back and check for actual duplicates.
• On the other hand, if $h(a_i) \neq h(a_j)$, it's necessarily true that the elements are NOT equal. $a_i$ and $a_j$ are stored in separate locations in the hash table.
• Think about the worst case test case; what would happen as you build up the hash table?

Answer 2

Quite interestingly, element distinctness problem has been asked recently, see here.

To summarize: A lower bound of $\Omega(n\log(n))$ can be proven via decision tree, therefore you were right to say approach 2) cannot be improved (if your only tool is comparing two elements).

---

In your problem, you need to use the fact $h(a_i) \rightarrow \{1 \dots n\}.$ How?

1. Create $n$ bins $B_1 ... B_n$

2. Go through your array and map each $a_i$ to the $j$-th bin, if $h(a_i)=j$. Additionally, each bin saves all the indexes of the elements mapped to its respective value.

3. If for every $i$, $B_i = 1$ you are done and can determine the set is distinct.

4. Else, for every $i$ s.t $B_i > 1$, you compare all the indexes of the elements that hash to $i$. If you find two that are equal, you can determine the set is not distinct. Continue until all collisions are checked, then determine the set is distinct.

It should be clear steps 1,2,3 take $O(n)$ in total, assuming $h$ outputs a value in constant time.

What about step 4?

For every "useless" comparison we make - that is a comparison between two distinct elements that hash to the same bin - there is some pair $(i,j)$ that fulfills $a_i \neq a_j$ and $h(a_i) = h(a_j)$, and we compare it only once.

So in step 4 we make a total of $m$ comparisons. Therefore the runtime would be $O(n+m)$.