4Sum II: Hash Map Meet-in-the-Middle
LeetCode 4Sum II (problem 454) gives you four integer arrays nums1, nums2, nums3, and nums4, all of length n. You need to count how many tuples (i, j, k, l) satisfy nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0.
Unlike 4Sum, you are not working with a single array. The four arrays are separate, and you only need the count of valid tuples, not the tuples themselves. This changes the optimal strategy entirely.
The problem
Given four arrays of integers, each of length n, count the number of tuples (i, j, k, l) such that:
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
Example: nums1 = [1, 2], nums2 = [-2, -1], nums3 = [-1, 2], nums4 = [0, 2]. Answer: 2. The two valid tuples are (1, 1, 0, 0) and (0, 0, 0, 1).
Why this problem matters
4Sum II is a clean example of the meet-in-the-middle technique. You split a large search space into two halves, precompute one half, and then search the other half against it. This pattern shows up in cryptography, optimization problems, and subset-sum variants. It also reinforces how hash maps can replace brute-force enumeration when you need to match complements.
The key insight
A brute-force approach would use four nested loops: O(n^4) time. That is far too slow for typical constraints where n can be up to 200.
The trick is to split the four arrays into two groups:
- Group 1:
nums1andnums2. Compute every possiblenums1[i] + nums2[j]sum. - Group 2:
nums3andnums4. Compute every possiblenums3[k] + nums4[l]sum.
For each sum s in Group 1, you store how many times it appears in a hash map. Then for each sum t in Group 2, you check whether -t exists in the map. If it does, you add its count to the result. This works because s + t = 0 means s = -t.
This is the meet-in-the-middle technique. Instead of exploring all n^4 combinations, you explore n^2 pairs from Group 1 and n^2 pairs from Group 2, bringing the total time down to O(n^2).
The code
def fourSumCount(self, nums1, nums2, nums3, nums4):
count = {}
for a in nums1:
for b in nums2:
s = a + b
count[s] = count.get(s, 0) + 1
result = 0
for c in nums3:
for d in nums4:
target = -(c + d)
result += count.get(target, 0)
return result
Why this works
The first pair of nested loops iterates over every combination of elements from nums1 and nums2. For each sum, the hash map records how many different (i, j) pairs produce that sum. If three different pairs all sum to 5, the map stores {5: 3}.
The second pair of nested loops iterates over every combination from nums3 and nums4. For each pair (k, l), you compute -(nums3[k] + nums4[l]) and look it up in the map. If that value exists with count 3, it means there are 3 different (i, j) pairs that, combined with this (k, l), produce a total sum of zero. You add all 3 to the result.
The beauty of this approach: you never need to track which specific indices form valid tuples. The count in the hash map captures all the information you need.
Visual walkthrough
Let's trace through the algorithm with nums1 = [1, 2], nums2 = [-2, -1], nums3 = [-1, 2], nums4 = [0, 2].
Step 1: Compute all A[i] + B[j] sums and store counts in a hash map
Four pairs produce four sums. Sum -1 appears once, 0 appears once, 1 appears once, -3 appears once.
Step 2: For each C[k] + D[l], check if -(C[k]+D[l]) exists in the map
C[0]+D[0] = -1. Need -(-1) = 1 in the map. Found with count 1. C[0]+D[1] = 1. Need -(1) = -1. Found with count 1.
Step 3: Sum up all matching counts
Only two C+D pairs had complements in the map. Add their counts: 1 + 1 = 2.
Step 4: Return the final count
There are 2 tuples (i,j,k,l) where A[i]+B[j]+C[k]+D[l] = 0: (1,1,0,0) and (0,0,0,1).
The hash map from Group 1 contains {-1: 1, 0: 2, 1: 1}. When scanning Group 2, two of the four (k, l) pairs find their complement in the map, contributing a total count of 2.
Complexity analysis
| Approach | Time | Space |
|---|---|---|
| Brute force (four nested loops) | O(n^4) | O(1) |
| Meet-in-the-middle with hash map | O(n^2) | O(n^2) |
Time: O(n^2). The first double loop over nums1 and nums2 runs n^2 iterations. The second double loop over nums3 and nums4 also runs n^2 iterations. Each hash map operation is O(1) on average.
Space: O(n^2). The hash map can store up to n^2 distinct sums from the first group. In practice, if many pairs produce the same sum, the map is smaller.
Building blocks
Hash map for complement lookup
This is the same core idea behind Two Sum. In Two Sum, you store seen values and look up complements. Here, you store pairwise sums and look up pairwise complements. The hash map turns an O(n) search into O(1) per query.
Meet-in-the-middle decomposition
The technique of splitting a problem into two halves, precomputing one half, and searching the other against it is powerful beyond this problem. Any time you have a product of search spaces that can be divided into two independent groups, consider this approach. The time drops from O(N) to O(sqrt(N)) in terms of the full search space.
Counting instead of collecting
Because the problem asks only for the count (not the actual tuples), you can store counts in the hash map rather than lists of index pairs. This keeps the solution simple and avoids unnecessary memory usage.
Edge cases
- All zeros. If every array is
[0, 0, ..., 0]with lengthn, every tuple is valid. The answer is n^4. The hash map stores{0: n^2}, and each of the n^2 lookups from Group 2 adds n^2 to the result. - No valid tuples. If no combination sums to zero, the hash map lookups return 0 every time, and the result stays 0.
- Single-element arrays. When
n = 1, there is exactly one tuple(0, 0, 0, 0). The algorithm handles this naturally with one iteration per loop. - Large values. The sums can range from very negative to very positive. Python handles arbitrary integers, so overflow is not a concern. In languages like Java or C++, ensure you use a data type that can hold the sum of four integers without overflow.
From understanding to recall
The core of 4Sum II is recognizing that you can split four arrays into two pairs and use a hash map as the bridge. The pattern is: precompute one side, query the other side. Once you see this decomposition, the code writes itself in a few lines.
What makes this problem tricky under time pressure is choosing the right approach. If you try sorting and two-pointer techniques (like in 4Sum or 3Sum), you will struggle because the elements come from separate arrays, not one shared array. The hash map approach is the natural fit here.
Practice until the split feels automatic: when you see multiple independent arrays that need to combine to a target, think "precompute half, query half."