LeetCode 454 - 4Sum II

The problem gives four integer arrays, nums1, nums2, nums3, and nums4, each containing n elements. We must count how many index tuples (i, j, k, l) satisfy: The important detail is that we are counting tuples of indices, not unique value combinations.

leetcodemediumarrayhash-table

LeetCode Problem 454

Difficulty: 🟡 Medium
Topics: Array, Hash Table

Solution

Problem Understanding

The problem gives four integer arrays, nums1, nums2, nums3, and nums4, each containing n elements. We must count how many index tuples (i, j, k, l) satisfy:

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

The important detail is that we are counting tuples of indices, not unique value combinations. If the same value appears multiple times in an array, every valid index combination contributes separately to the answer.

A direct interpretation is that we must examine all possible ways to pick one element from each array and determine whether their sum equals zero. Since each array has length n, the total number of combinations is:

n * n * n * n = n^4

The constraints tell us that:

1 <= n <= 200

If we attempted all 200^4 = 1,600,000,000 combinations, the solution would be far too slow. This immediately suggests that a brute-force approach is not feasible.

The values in the arrays can be negative, positive, or zero. This matters because there is no ordering or monotonic behavior we can exploit with sorting and two pointers directly across four arrays. Instead, the problem strongly suggests using hashing to store partial sums.

Several edge cases are important:

  • Arrays may contain duplicate values, which means frequencies matter.
  • Arrays may contain all zeros, which creates many valid tuples.
  • Negative numbers and positive numbers can cancel each other out in many ways.
  • Multiple different pairs may produce the same sum, so counting frequencies correctly is essential.
  • The answer can become large because many combinations may be valid.

Approaches

Brute Force Approach

The most straightforward solution is to try every possible tuple (i, j, k, l).

We use four nested loops:

  • The first loop chooses an element from nums1
  • The second loop chooses an element from nums2
  • The third loop chooses an element from nums3
  • The fourth loop chooses an element from nums4

For every combination, we compute:

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

If the sum equals zero, we increment the answer.

This approach is correct because it explicitly checks every possible tuple. However, it is computationally expensive. With n = 200, the algorithm requires up to 200^4 operations, which is far too large for practical execution.

Optimal Approach

The key observation is that the equation:

a + b + c + d = 0

can be rearranged as:

a + b = -(c + d)

Instead of considering four numbers at once, we can split the problem into two independent pair-sum problems.

We first compute all possible sums from nums1 and nums2 and store how many times each sum occurs in a hash map.

Then, for every possible sum from nums3 and nums4, we check whether its negation exists in the hash map.

For example:

If nums3[k] + nums4[l] = 5
Then we need a pair from nums1 and nums2 whose sum is -5

This reduces the complexity dramatically:

  • Computing pair sums takes O(n^2)
  • Looking up complements also takes O(n^2)

The total becomes O(n^2) instead of O(n^4).

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n^4) O(1) Checks every possible tuple directly
Optimal O(n^2) O(n^2) Uses a hash map to store pair sums

Algorithm Walkthrough

  1. Create a hash map called pair_sum_count.

The keys will be sums formed by elements from nums1 and nums2. The values will represent how many times each sum appears. 2. Iterate through every element in nums1.

For each element, iterate through every element in nums2. 3. Compute the pair sum.

For every pair (a, b):

current_sum = a + b

Increment the frequency of this sum in the hash map. 4. Initialize a variable called result to zero.

This variable will store the total number of valid tuples. 5. Iterate through every element in nums3.

For each element, iterate through every element in nums4. 6. Compute the current sum from the second pair.

current_sum = c + d
  1. Find the complementary sum.

To satisfy:

a + b + c + d = 0

we need:

a + b = -(c + d)

So we compute:

target = -current_sum
  1. Check the hash map.

If target exists in the hash map, add its frequency to result.

This works because every occurrence of target represents a valid pair from the first two arrays. 9. Return result.

Why it works

The algorithm works because every valid tuple can be uniquely decomposed into:

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

The hash map stores exactly how many ways the first half of the equation can produce a given sum. For every second-half pair sum, we look for the exact complementary value needed to make the total zero. Since all pair combinations are considered, every valid tuple is counted exactly once.

Python Solution

from collections import defaultdict
from typing import List

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

        # Store all sums from nums1 and nums2
        for num1 in nums1:
            for num2 in nums2:
                pair_sum_count[num1 + num2] += 1

        result = 0

        # Find complementary sums from nums3 and nums4
        for num3 in nums3:
            for num4 in nums4:
                target = -(num3 + num4)

                if target in pair_sum_count:
                    result += pair_sum_count[target]

        return result

The implementation begins by creating a hash map using defaultdict(int). This allows frequencies to be incremented easily without checking whether a key already exists.

The first nested loop generates all possible sums from nums1 and nums2. Each sum is stored along with its frequency. If the same sum appears multiple times, the count increases accordingly.

The second nested loop processes all pair sums from nums3 and nums4. For every pair, the algorithm computes the complementary value needed to make the total sum equal zero.

If this complementary value exists in the hash map, its frequency is added to the result. This automatically counts all matching tuples formed by the stored pairs.

Finally, the algorithm returns the total count of valid tuples.

Go Solution

func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {
	pairSumCount := make(map[int]int)

	// Store all sums from nums1 and nums2
	for _, num1 := range nums1 {
		for _, num2 := range nums2 {
			pairSumCount[num1+num2]++
		}
	}

	result := 0

	// Find complementary sums from nums3 and nums4
	for _, num3 := range nums3 {
		for _, num4 := range nums4 {
			target := -(num3 + num4)

			if count, exists := pairSumCount[target]; exists {
				result += count
			}
		}
	}

	return result
}

The Go implementation follows the same logic as the Python version. The main difference is that Go uses an explicit map[int]int instead of defaultdict.

When checking for a complement, Go uses the two-value map lookup syntax:

count, exists := pairSumCount[target]

This safely determines whether the key exists before using the value.

The constraints are small enough that integer overflow is not a concern in Go for standard int types.

Worked Examples

Example 1

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

Step 1: Build Pair Sums from nums1 and nums2

num1 num2 Sum Hash Map State
1 -2 -1 {-1: 1}
1 -1 0 {-1: 1, 0: 1}
2 -2 0 {-1: 1, 0: 2}
2 -1 1 {-1: 1, 0: 2, 1: 1}

Final hash map:

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

Step 2: Process nums3 and nums4

num3 num4 Sum Target Matches in Map Result
-1 0 -1 1 1 1
-1 2 1 -1 1 2
2 0 2 -2 0 2
2 2 4 -4 0 2

Final answer:

2

Example 2

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

Step 1: Build Pair Sums

num1 num2 Sum Hash Map State
0 0 0 {0: 1}

Step 2: Process Remaining Pairs

num3 num4 Sum Target Matches Result
0 0 0 0 1 1

Final answer:

1

Complexity Analysis

Measure Complexity Explanation
Time O(n^2) Two nested loops for pair sums and another two nested loops for complement checks
Space O(n^2) The hash map may store up to all distinct pair sums

The algorithm computes all pair sums from the first two arrays and all pair sums from the second two arrays. Each phase requires n^2 operations, resulting in overall O(n^2) time complexity.

The hash map can contain up to n^2 distinct sums in the worst case, so the space complexity is also O(n^2).

Test Cases

from typing import List

class Solution:
    def fourSumCount(
        self,
        nums1: List[int],
        nums2: List[int],
        nums3: List[int],
        nums4: List[int]
    ) -> int:
        from collections import defaultdict

        pair_sum_count = defaultdict(int)

        for num1 in nums1:
            for num2 in nums2:
                pair_sum_count[num1 + num2] += 1

        result = 0

        for num3 in nums3:
            for num4 in nums4:
                result += pair_sum_count.get(-(num3 + num4), 0)

        return result

sol = Solution()

assert sol.fourSumCount(
    [1, 2],
    [-2, -1],
    [-1, 2],
    [0, 2]
) == 2  # Provided example with two valid tuples

assert sol.fourSumCount(
    [0],
    [0],
    [0],
    [0]
) == 1  # Single-element arrays with one valid tuple

assert sol.fourSumCount(
    [1],
    [1],
    [1],
    [1]
) == 0  # No possible zero sum

assert sol.fourSumCount(
    [0, 0],
    [0, 0],
    [0, 0],
    [0, 0]
) == 16  # Every combination is valid

assert sol.fourSumCount(
    [-1, -1],
    [1, 1],
    [0, 0],
    [0, 0]
) == 16  # Duplicate values create multiple tuples

assert sol.fourSumCount(
    [100000000],
    [-100000000],
    [0],
    [0]
) == 1  # Large magnitude values

assert sol.fourSumCount(
    [1, -1],
    [-1, 1],
    [0, 0],
    [0, 0]
) == 8  # Multiple complementary pair sums

assert sol.fourSumCount(
    [2],
    [-2],
    [3],
    [-3]
) == 1  # Exact cancellation across all arrays

print("All test cases passed.")

Test Summary

Test Why
Provided example 1 Verifies standard functionality
Provided example 2 Verifies minimal input size
All positive numbers Ensures zero is not falsely counted
All zeros Tests maximum duplicate tuple generation
Duplicate values Verifies frequency counting correctness
Large magnitude values Confirms handling of large integers
Mixed positive and negative Tests multiple complement matches
Exact cancellation Verifies basic correctness

Edge Cases

One important edge case occurs when all arrays contain only zeros. In this scenario, every possible tuple is valid because the sum is always zero. A buggy implementation might accidentally count only unique sums instead of all index combinations. The hash map frequency approach handles this correctly because it stores how many times each pair sum occurs, not just whether it exists.

Another critical edge case involves duplicate values. For example:

nums1 = [-1, -1]
nums2 = [1, 1]

The sum 0 can be formed multiple times. A solution that stores only unique sums would undercount the answer. The implementation correctly tracks frequencies in the hash map, ensuring every valid combination contributes to the final result.

A third edge case occurs when no valid tuples exist. For example:

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

The total sum can never equal zero. The algorithm handles this naturally because no complementary sums are found in the hash map, so the result remains zero.

Another subtle case involves negative numbers and large magnitudes. Since the problem allows both positive and negative integers, complementary matching is essential. The implementation correctly computes:

target = -(num3 + num4)

which ensures that negative and positive sums are paired properly regardless of sign.