# LeetCode 454: 4Sum II

## Problem Restatement

We are given four integer arrays:

```python
nums1
nums2
nums3
nums4
```

All four arrays have the same length `n`.

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

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

and:

```python
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

| Item | Meaning |
|---|---|
| Input | Four integer arrays `nums1`, `nums2`, `nums3`, and `nums4` |
| Output | Number of tuples `(i, j, k, l)` with sum `0` |
| Array length | All arrays have length `n` |
| Important detail | Equal values at different indices count as different choices |

Function shape:

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

## Examples

Example 1:

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

The valid tuples are:

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

So the answer is:

```python
2
```

Example 2:

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

There is only one tuple:

```python
(0, 0, 0, 0)
```

The sum is:

```python
0 + 0 + 0 + 0 = 0
```

So the answer is:

```python
1
```

Example 3:

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

The only possible sum is:

```python
1 + 1 + 1 + 1 = 4
```

So the answer is:

```python
0
```

## First Thought: Brute Force

The most direct solution is to try every possible tuple.

There are four indices:

```python
i, j, k, l
```

So we can use four nested loops:

```python
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:

```python
n * n * n * n = n^4
```

tuples.

So the brute force time complexity is:

```python
O(n^4)
```

This grows too quickly.

For example, if `n = 200`, then:

```python
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:

```python
a + b + c + d = 0
```

We can split it into two pair sums:

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

So:

```python
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:

```python
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`:

```python
pair_count[a + b] += 1
```

Then initialize:

```python
answer = 0
```

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

```python
need = -(c + d)
```

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

So add:

```python
pair_count[need]
```

to the answer.

Finally, return `answer`.

## Walkthrough

Use the standard example:

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

First, build sums from `nums1` and `nums2`.

| `a` | `b` | `a + b` |
|---:|---:|---:|
| 1 | -2 | -1 |
| 1 | -1 | 0 |
| 2 | -2 | 0 |
| 2 | -1 | 1 |

So the map becomes:

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

Now scan pairs from `nums3` and `nums4`.

| `c` | `d` | `c + d` | Needed sum from first two arrays | Add |
|---:|---:|---:|---:|---:|
| -1 | 0 | -1 | 1 | 1 |
| -1 | 2 | 1 | -1 | 1 |
| 2 | 0 | 2 | -2 | 0 |
| 2 | 2 | 4 | -4 | 0 |

Total:

```python
1 + 1 + 0 + 0 = 2
```

So the answer is:

```python
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:

```python
nums1[i] + nums2[j]
```

and a second pair:

```python
nums3[k] + nums4[l]
```

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

```python
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.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n^2)` | Build `n^2` sums, then scan `n^2` more pairs |
| Space | `O(n^2)` | The hash map may store up to `n^2` distinct pair sums |

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

## Implementation

```python
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:

```python
pair_count = defaultdict(int)
```

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

Then:

```python
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:

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

So sum `0` has count `2`.

Next:

```python
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:

```python
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.

```python
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

```python
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:

| Test | Why |
|---|---|
| Standard example | Confirms normal counting |
| Four single zero arrays | Smallest valid positive count |
| No zero-sum tuple | Confirms answer can be `0` |
| All zeros with duplicates | Counts index tuples, not unique values |
| Mixed duplicates and negatives | Checks repeated sums correctly |