# Counting common values in two arrays

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.

## 1 Answer

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
• 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? Aug 25, 2019 at 22:15
• Perhaps you should try in on some example and see what happens. Plus, there’s always the possibility I made some mistake. Aug 25, 2019 at 22:17
• 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? Aug 25, 2019 at 22:23
• Hope it’s clearer now. Aug 25, 2019 at 22:24
• Impressive ( from my perspective) . Thanks a lot! Aug 25, 2019 at 23:00