LeetCode 454 · Hashing

4Sum II, explained with a picture

Four bags of numbered balls that cancel out.

Hashing
▶ Watch it step by step

The problem

Given four lists, count the choices (one number from each) that add up to 0.

Input:  A = [1, 2], B = [−2, −1], C = [−1, 2], D = [0, 2]
Output: 2

Picture it

Picture four bags of numbered balls. Trying every 4-way pick is slow. Instead, record every A + B sum in a tally, then for every C + D sum look up how many A + B sums cancel it.

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

The key idea

Meet in the middle: O(n²) instead of O(n⁴).

Python solution

def four_sum_count(a, b, c, d):
    ab = Counter()
    for x in a:
        for y in b:
            ab[x + y] += 1
    count = 0
    for x in c:
        for y in d:
            count += ab[-(x + y)]
    return count

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.