#454
4Sum II
Medium Meet in the middle with HashMap
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Given four arrays of equal length, count tuples (i, j, k, l) with a[i] + b[j] + c[k] + d[l] == 0.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: count (i, j, k, l) with a + b + c + d = 0 from four arrays.
Why this works: store counts of every a + b, then for every c + d look up its negative. n⁴ becomes n².
Example: A [1,2], B [-2,-1], C [-1,2], D [0,2]
a+b sums: -1, 0, 0, 1c+d sums: -1, 1, 2, 4 → need 1, -1, -2, -4matches: 1 → 1, -1 → 1 → total 2
✦Hints open one at a time
Four loops are O(n⁴).
Count every sum a[i] + b[j] in a map.
For every c[k] + d[l], look up its negative.
↗Approach
Split into two halves: store counts of all pairwise sums from a and b, then for each pair from c and d add map[−(c + d)].
</>Solution (Java)
import java.util.*;
class Solution {
public int fourSumCount(int[] a, int[] b, int[] c, int[] d) {
Map<Integer, Integer> ab = new HashMap<>();
for (int x : a)
for (int y : b) ab.merge(x + y, 1, Integer::sum);
int count = 0;
for (int x : c)
for (int y : d) count += ab.getOrDefault(-(x + y), 0);
return count;
}
}!Common mistake
Using a set instead of a count map, which ignores pairs with equal sums.
Complexity
- Time: O(n²).
- Space: O(n²).
Topic: Hashing
🎬 Episodes 37–39: video coming soon