1
$\begingroup$

given two arrays of integers A and B of size m, with values in the range [-n,n]. I want an algorithm to count how many common values are in A and B , if a value is repeated we only count it once , for example : $A=\{2,2,14,3\}$ and $B=\{1,2,14,14,5\}$ the algorithm should return 2 . Problem is I need to do this in $O(m)$ time.

My attempt was to create an array $C$, of size $2n$. and increment all the values of $A$ and $B$ by $n$, and count the values of $A$ like: $C[A[i]] = 1$ that would take me $O(m)$ time , and $O(1)$ time to create the array. then going over $B$ and counting how many $1's$ I encounter in $C$.

So far it sounds good, however I have no idea what's in $C$ in the first place and it could be that there's a $1$ in there already and that would increment the counter falsely , and initializing $C$ would take $O(n)$ time.

Any ideas? Thanks ahead.

$\endgroup$
4
$\begingroup$

Try the following algorithm:

  1. For $1 \leq i \leq m$: $C[A[i]] = 0$
  2. For $1 \leq i \leq m$: $C[B[i]] = 1$
  3. Initialize answer to $0$
  4. For $1 \leq i \leq m$:
    • If $C[A[i]] = 1$ then $C[A[i]] = 2$ and increment answer
  5. Return answer
$\endgroup$
  • $\begingroup$ Could you further explain what 4 means? And could it be that 1 will overwrite 0 in C if there is a value in both A and B? $\endgroup$ – sadElephent Aug 25 at 22:15
  • $\begingroup$ Perhaps you should try in on some example and see what happens. Plus, there’s always the possibility I made some mistake. $\endgroup$ – Yuval Filmus Aug 25 at 22:17
  • $\begingroup$ Well I don’t understand what you mean by if $C[A[i]] = 1: C[A[i]] = 2$ , increment answer what’s the condition and what is the consequent? $\endgroup$ – sadElephent Aug 25 at 22:23
  • $\begingroup$ Hope it’s clearer now. $\endgroup$ – Yuval Filmus Aug 25 at 22:24
  • $\begingroup$ Impressive ( from my perspective) . Thanks a lot! $\endgroup$ – sadElephent Aug 25 at 23:00

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.