LeetCode 454: 4Sum II

Problem Restatement

We are given four integer arrays:

nums1
nums2
nums3
nums4

All four arrays have the same length n.

We need to count how many tuples (i, j, k, l) satisfy:

0 <= i, j, k, l < n

and:

nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

The task asks for the number of valid index tuples, not the tuples themselves. The official statement defines the goal as counting tuples whose four selected values sum to zero.

Input and Output

Function shape:

def fourSumCount(
    nums1: list[int],
    nums2: list[int],
    nums3: list[int],
    nums4: list[int],
) -> int:
    ...

Examples

Example 1:

nums1 = [1, 2]
nums2 = [-2, -1]
nums3 = [-1, 2]
nums4 = [0, 2]

The valid tuples are:

(0, 0, 0, 1): 1 + (-2) + (-1) + 2 = 0
(1, 1, 0, 0): 2 + (-1) + (-1) + 0 = 0

So the answer is:

2

Example 2:

nums1 = [0]
nums2 = [0]
nums3 = [0]
nums4 = [0]

There is only one tuple:

(0, 0, 0, 0)

The sum is:

0 + 0 + 0 + 0 = 0

So the answer is:

1

Example 3:

nums1 = [1]
nums2 = [1]
nums3 = [1]
nums4 = [1]

The only possible sum is:

1 + 1 + 1 + 1 = 4

So the answer is:

0

First Thought: Brute Force

The most direct solution is to try every possible tuple.

There are four indices:

i, j, k, l

So we can use four nested loops:

class Solution:
    def fourSumCount(
        self,
        nums1: list[int],
        nums2: list[int],
        nums3: list[int],
        nums4: list[int],
    ) -> int:
        count = 0

        for a in nums1:
            for b in nums2:
                for c in nums3:
                    for d in nums4:
                        if a + b + c + d == 0:
                            count += 1

        return count

This is easy to understand.

It checks every possible choice from the four arrays.

Problem With Brute Force

If each array has length n, then there are:

n * n * n * n = n^4

tuples.

So the brute force time complexity is:

O(n^4)

This grows too quickly.

For example, if n = 200, then:

200^4 = 1,600,000,000

That is already far too many checks.

We need to reduce the four-array problem into something smaller.

Key Insight

The equation is:

a + b + c + d = 0

We can split it into two pair sums:

(a + b) + (c + d) = 0

So:

a + b = -(c + d)

This is the main idea.

Instead of checking all four numbers at once, we count all possible sums from nums1 and nums2.

Then for every pair from nums3 and nums4, we ask:

How many earlier pairs have sum equal to -(c + d)?

This turns a four-loop problem into two two-loop passes.

Algorithm

Create a hash map called pair_count.

The key is a pair sum from nums1 and nums2.

The value is how many index pairs produce that sum.

For every a in nums1 and every b in nums2:

pair_count[a + b] += 1

Then initialize:

answer = 0

For every c in nums3 and every d in nums4, compute:

need = -(c + d)

If need appears in pair_count, then every pair (a, b) with that sum forms a valid tuple.

So add:

pair_count[need]

to the answer.

Finally, return answer.

Walkthrough

Use the standard example:

nums1 = [1, 2]
nums2 = [-2, -1]
nums3 = [-1, 2]
nums4 = [0, 2]

First, build sums from nums1 and nums2.

So the map becomes:

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

Now scan pairs from nums3 and nums4.

Total:

1 + 1 + 0 + 0 = 2

So the answer is:

2

Correctness

The algorithm counts all valid tuples by splitting each tuple into two parts.

Every tuple (i, j, k, l) has a first pair:

nums1[i] + nums2[j]

and a second pair:

nums3[k] + nums4[l]

The tuple is valid exactly when these two sums are opposites:

nums1[i] + nums2[j] = -(nums3[k] + nums4[l])

The hash map stores the number of first-pair index choices for every possible sum.

When the algorithm examines a second pair (k, l), it looks up the exact first-pair sum needed to make the total zero.

If the needed sum appears x times, then there are exactly x valid choices for (i, j) with this fixed (k, l).

Adding this value for every (k, l) counts every valid tuple once.

Therefore, the algorithm returns the exact number of tuples whose total sum is zero.

Complexity

Let n be the length of each array.

This is a large improvement over O(n^4) brute force.

Implementation

from collections import defaultdict

class Solution:
    def fourSumCount(
        self,
        nums1: list[int],
        nums2: list[int],
        nums3: list[int],
        nums4: list[int],
    ) -> int:
        pair_count = defaultdict(int)

        for a in nums1:
            for b in nums2:
                pair_count[a + b] += 1

        answer = 0

        for c in nums3:
            for d in nums4:
                answer += pair_count[-(c + d)]

        return answer

Code Explanation

We use:

pair_count = defaultdict(int)

This lets us increment missing keys without checking whether they already exist.

Then:

for a in nums1:
    for b in nums2:
        pair_count[a + b] += 1

counts every possible pair sum from the first two arrays.

If two different pairs have the same sum, the count increases.

For example:

1 + (-1) = 0
2 + (-2) = 0

So sum 0 has count 2.

Next:

for c in nums3:
    for d in nums4:
        answer += pair_count[-(c + d)]

For each pair from the last two arrays, we compute the opposite sum.

If no first-pair sum matches, defaultdict(int) returns 0.

If there are matches, we add the number of matching first pairs.

Finally:

return answer

returns the total number of valid tuples.

Alternative Implementation With Counter

Python also has Counter, which is a good fit for counting pair sums.

from collections import Counter

class Solution:
    def fourSumCount(
        self,
        nums1: list[int],
        nums2: list[int],
        nums3: list[int],
        nums4: list[int],
    ) -> int:
        pair_count = Counter(a + b for a in nums1 for b in nums2)

        answer = 0

        for c in nums3:
            for d in nums4:
                answer += pair_count[-c - d]

        return answer

This version is shorter, but the explicit defaultdict version is usually better for learning.

Testing

def run_tests():
    s = Solution()

    assert s.fourSumCount(
        [1, 2],
        [-2, -1],
        [-1, 2],
        [0, 2],
    ) == 2

    assert s.fourSumCount(
        [0],
        [0],
        [0],
        [0],
    ) == 1

    assert s.fourSumCount(
        [1],
        [1],
        [1],
        [1],
    ) == 0

    assert s.fourSumCount(
        [0, 0],
        [0, 0],
        [0, 0],
        [0, 0],
    ) == 16

    assert s.fourSumCount(
        [-1, -1],
        [-1, 1],
        [-1, 1],
        [1, -1],
    ) == 6

    print("all tests passed")

run_tests()

Test meaning: