Finding common elements in two arrays of different size

Question

I have a problem to find common elements in two arrays and that's of different size.

Take , Array A1 of size n and Array A2 of size m, and m != n

So far, I've tried to iterate lists one by one and copy elements to another list. If the element already contains mark it, but I know it's not a good solution.

Answer 1

Sort the arrays. Then iterate through them with two pointers, always advancing the one pointing to the smaller value. When they point to equal values, you have a common value. This will be O(n log n+m log m) where n and m are the sizes of the two lists. It's just like a merge in merge sort, but where you only produce output when the values being pointed to are equal.

def common_elements(a, b):
  a.sort()
  b.sort()
  i, j = 0, 0
  common = []
  while i < len(a) and j < len(b):
    if a[i] == b[j]:
      common.append(a[i])
      i += 1
      j += 1
    elif a[i] < b[j]:
      i += 1
    else:
      j += 1
  return common

print 'Common values:', ', '.join(map(str, common_elements([1, 2, 4, 8], [1, 4, 9])))

outputs

Common values: 1, 4

If the elements aren't comparable, throw the elements from one list into a hashmap and check the elements in the second list against the hashmap.

Answer 2

If you want to make it efficient I would convert the smaller array into a hashset and then iterate the larger array and check whether the current element was contained in the hashset. The hash function is efficient compared to sorting arrays. Sorting arrays is expensive.

Here's my sample code

import java.util.*;
public class CountTest {     
    public static void main(String... args) {        
        Integer[] array1 = {9, 4, 6, 2, 10, 10};
        Integer[] array2 = {14, 3, 6, 9, 10, 15, 17, 9};                    
        Set hashSet = new HashSet(Arrays.asList(array1)); 
        Set commonElements = new HashSet();        
        for (int i = 0; i < array2.length; i++) {
            if (hashSet.contains(array2[i])) {
                commonElements.add(array2[i]);
            }
        }
        System.out.println("Common elements " + commonElements);
    }    
}

Output:

Common elements [6, 9, 10]