LeetCode 349 · Hashing

Intersection of Two Arrays, explained with a picture

Who is on both guest lists?.

Hashing
▶ Watch it step by step

The problem

Return the numbers that appear in both lists, each listed once.

Input:  A = [4, 9, 5], B = [9, 4, 9, 8, 4]
Output: [4, 9]

Picture it

Picture two guest lists. Turn list A into a set; walk through B and keep every guest that is in the set (only once).

Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.

The key idea

Set membership. O(m + n).

Python solution

def intersection(a, b):
    seen = set(a)
    out = set()
    for x in b:
        if x in seen:
            out.add(x)
    return list(out)

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.