# 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.

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
• 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? – sadElephent Aug 25 at 22:23