454. 4Sum II — DSA Atlas

454

MediumArrays and HashingHash map of pairwise sumsMeet in the middle with a sum-frequency map

4Sum II

Given four integer arrays nums1, nums2, nums3, nums4, each of length n, count the number of index tuples (i, j, k, l) such that nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0.

Open official problem prompt ↗

In plain English

Count all four-index combinations, one index per array, whose four values sum to zero.

Picture it like this

Split four dice into two pairs. Write down how many ways each total appears for the first pair, then for every total of the second pair look up how many first-pair totals cancel it out.

Example

Input: nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
Output: 2
Why: The two valid tuples are (0,0,0,1): 1 + (-2) + (-1) + 2 = 0, and (1,1,0,0): 2 + (-1) + (-1) + 0 = 0.

Constraints

n == nums1.length == nums2.length == nums3.length == nums4.length1 <= n <= 200-2^28 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 2^28

Pattern lesson

See the pattern, then code

Meet in the middle with a sum-frequency map

↗

Arrays and Hashing

Duplicates, frequency counts, grouping, membership tests, or pair lookup.. A + B + C + D = 0 means (A + B) = -(C + D). Precompute how many ways each value of A+B occurs, then for every C+D look up how many A+B pairs equal its negation.

New words, made simpleKnow these before the algorithm

Meet in the middle: Split an exponential/high-degree search into two halves, precompute one half, and match against it.
Frequency map: A dictionary from a value to how many times it occurs, enabling O(1) count lookups.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Brute force quadruple loop

At n=200 that is 1.6 billion iterations; far too slow.

Try every (i,j,k,l) and test the sum.

Time O(n^4)Space O(1)

Best choiceTwo-and-two with a hash map

Reduces 4 nested loops to 2 + 2 by trading time for a sum-frequency table.

Hash all A+B sums, then scan all C+D sums and look up the negation.

Time O(n^2)Space O(n^2)

The rule we keep true

Invariant

After building first, first[s] equals the exact number of (i, j) pairs with nums1[i] + nums2[j] == s.

Why this is correct

Reasoning

Every valid quadruple splits uniquely into a first-half sum s = A+B and a second-half sum -s = C+D. Summing first[-(c+d)] over all (c,d) pairs counts, for each second-half pair, precisely the number of first-half pairs that complete it to zero, so the total equals the number of valid quadruples.

The algorithm in three movesSay these aloud before coding

1Build a Counter of every sum a + b over nums1 x nums2

first = {-1:1, 0:2, 1:1}

2Initialize a running count to 0

c+d=-1 -> need 1 -> +1

3For each pair (c, d) over nums3 x nums4, add the frequency of -(c + d) from the Counter

c+d=1 -> need -1 -> +1; total = 2

4Return the accumulated count

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

-10

1 · Readnums1 x nums2

2 · AskWhat are all a+b sums?

3 · Update state1-2=-1, 1-1=0, 2-2=0, 2-1=1

4 · Resultfirst = {-1:1, 0:2, 1:1}

Key takeaway

The four boxes are the A+B sums {-1,0,0,1}; each C+D query looks up the negated value's frequency.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 5Precompute half sums
A Counter over the cross product of the first two arrays records the multiplicity of every A+B value.
2
Lines 7-9Match the second half
For each C+D, first[-(c+d)] returns 0 for absent keys (Counter default), so we safely accumulate the number of completing pairs.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

No tuple sums to zero -> return 0
Many pairs share the same sum, so counts multiply (Counter values exceed 1)
Negative and positive values that cancel across halves
n = 1: a single quadruple, counted if it sums to zero

Common beginner mistakes

Deduplicating sums instead of counting multiplicity, which undercounts tuples that repeat a sum
Using a plain dict and getting KeyError instead of Counter's 0 default
Trying to also enforce distinct values; the problem counts index tuples, not distinct values
Forgetting the negation and looking up (c+d) instead of -(c+d)

Check your understanding

Why must first store counts rather than just the set of achievable sums?

4Sum II

4Sum II

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Arrays and Hashing