FAANG · LeetCode #454

4Sum II — three-stage drill

1The ProblemMedium

4Sum II

Count tuples (a,b,c,d), one from each array, summing to zero.

Examples

A=[1,2] B=[-2,-1] C=[-1,2] D=[0,2]→ 2

constraintFour arrays of equal length n; count index tuples, not values.

2The PatternTIME O(n) · SPACE O(n)

Arrays & Hashing

Trade space for time: a hash map turns 'have I seen this?' into an O(1) lookup.

Problems using this pattern

3The SolutionRESULT → 2

Step through it

build: 1 + (−2) = −1 → map[−1] = 1

Step 1 / 8

Python▎tally a+b · look up −(c+d)

1def fourSumCount(A, B, C, D):
2    cnt = {}
3    for a in A:
4        for b in B:
5            cnt[a + b] = cnt.get(a + b, 0) + 1
6    total = 0
7    for c in C:
8        for d in D:
9            total += cnt.get(-(c + d), 0)
10    return total

why it worksBrute force tries all four loops — O(n⁴). Split in half: tally every a+b sum from the first two arrays into a hash map (O(n²)). Then for each c+d, the rest must equal −(c+d) — and map[−(c+d)] says how many (a,b) pairs complete the zero. Two O(n²) passes → O(n²) total.

Arrow keys to navigate · escape to reset

All problems by pattern

Two Pointers

Sliding Window

Prefix Sum

Monotonic Deque

Shortest Subarray with Sum at Least K

Binary Search

Arrays & Hashing

Monotonic Stack

Intervals

4Sum II — three-stage drill

4Sum II

Arrays & Hashing

Step through it

All problems by pattern

Two Pointers

Sliding Window

Prefix Sum

Monotonic Deque

Binary Search

Arrays & Hashing

Monotonic Stack

Intervals

Heap / Top-K

Backtracking

Recursive Descent