LeetCode 350 · Hashing

Intersection of Two Arrays II, explained with a picture

Matching fruit from two baskets.

Hashing
▶ Watch it step by step

The problem

Return the intersection of two lists, where each value appears as many times as it is in both.

Input:  A = [1, 2, 2, 1], B = [2, 2]
Output: [2, 2]

Picture it

Picture two fruit baskets. Count each kind of fruit in basket A, then go through basket B and pair up a fruit whenever A still has one left.

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

The key idea

Counting dictionary, decrement on match. O(m + n).

Python solution

def intersect(a, b):
    count = Counter(a)
    out = []
    for x in b:
        if count[x] > 0:
            out.append(x)
            count[x] -= 1
    return out

LeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import Counter

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.