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 outLeetCode 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.