[Python] Intersection of Two Arrays

Find common elements in two arrays, i.e., intersection of two arrays in Python.

The idea is to convert one array to the data structure of key-value pairs, i.e., hash table. The hash table in Python is built-in dictionary type. Then we check if items of the other array is in the hash table. If yes, the item is in the intersection of the two arrays.

The following is the implementation of above idea.

Run Code on repl.it

def intersection(a, b):
      map = {}

      for x in a:
              map[x] = True

      intersection = []
      for x in b:
              if x in map:
                      intersection.append(x)

      return intersection


if __name__ == "__main__":
      a = [1, 2, 3, 4, 5]
      b = [2, 3, 5, 7, 11]
      print(intersection(a, b))

The result will be [2 3 5].

The same idea can be used to find union of two arrays. See [1].

Tested on:

• Ubuntu 17.10, Python 3.6.3
• repl.it - Python3 Compiler

References: