1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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?
$\endgroup$
2
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ Just adding: The fact that the elements are double is irrelevant, except you must make sure that h(+0) =h(-0). The fact that the number of hash values n equals the number of array elements n is also mostly irrelevant, except that you will need the larger in the big-O for the total runtime. Of course you can replace h(x) with h(x) modulo n. $\endgroup$ – gnasher729 Apr 26 at 11:06
  • $\begingroup$ @Iox I do not understand the runtime analysis of step 4. Suppose a bin contains all $m$ of such elements. Then we are back to the original problem, because we have to find out in $O(m)$ time if all elements are different !? $\endgroup$ – uawff Apr 27 at 15:08
  • $\begingroup$ @uawff if all the elements map to one bin, then $m=n^2$ and we perform $m$ comparisons. Note that the amount of comparisons we make in step 4 is at most one for every distinct pair that hash to the same bin, which is exactly the definition of $m$. $\endgroup$ – lox Apr 27 at 16:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.