How do I get the intersection between two arrays as a new array?

Question

I faced this problem many times during various situations. It is generic to all programming languages although I am comfortable with C or Java.

Let us consider two arrays (or collections):

char[] A = {'a', 'b', 'c', 'd'}; char[] B = {'c', 'd', 'e', 'f'}; 

How do I get the common elements between the two arrays as a new array? In this case, the intersection of array A and B is char[] c = {'c', 'd'}.

I want to avoid the repeated iteration of one array inside the other array which will increase the execution time by (length of A times length of B) which is too much in the case of huge arrays.

Is there any way we could do a single pass in each array to get the common elements?

Answer 1

foreach element e in array A     insert e into hash table H  foreach element e in array B     if H contains e          print e 

This algorithm is O(N) in time and O(N) in space.

To avoid the extra space, you can use the sorting based approach.