4Sum II — Meet in the Middle with a Frequency Map

Problem Statement#

Given four integer arrays nums1, nums2, nums3, nums4 all of length n, return the number of tuples (i, j, k, l) such that:

• 0 <= i, j, k, l < n
• nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

Constraints:

• n == nums1.length == nums2.length == nums3.length == nums4.length
• 1 <= n <= 200
• -2^28 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 2^28

Input:  nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
Output: 2
Explanation: (0,0,0,1): 1+(-2)+(-1)+2=0  and  (1,1,0,0): 2+(-1)+(-1)+0=0

Input:  nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
Output: 1

Why This Problem Matters#

4Sum II (LC 454) is one of the clearest demonstrations of the meet-in-the-middle algorithmic strategy. The naive approach — enumerate all n^4 tuples and check each sum — is O(n^4), which for n = 200 means 1.6 billion operations. Far too slow.

By splitting the problem into two halves: compute all n^2 pair sums from the first two arrays and store their frequencies, then for each pair from the last two arrays look up its negation. Total work is O(n^2) for building the map and O(n^2) for querying — O(n^2) overall.

Google and Amazon use this problem to see whether candidates can identify that splitting into two halves is often the right strategy for combinatorial counting problems. The pattern transfers directly to subset-sum problems, approximate nearest-neighbour search, and birthday-attack style cryptographic analyses.

At Microsoft, this problem tests "decomposition" skills: can you take a monolithic O(n^4) problem and decompose it into two independent O(n^2) parts? Candidates who immediately identify the split demonstrate senior-level algorithmic thinking.

The problem is also notable because it does not require deduplication — every tuple (i, j, k, l) with different indices is counted separately. This simplifies the implementation compared to the original "4Sum" problem (LC 18).

The Core Insight#

Meet in the Middle:

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

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

Phase 1: Compute all n^2 pair sums nums1[i] + nums2[j] and store their frequencies in ab_count.

Phase 2: For each pair (k, l) from nums3 and nums4, compute target = -(nums3[k] + nums4[l]) and look up ab_count[target]. Each match contributes that many valid tuples.

The answer is the sum of all ab_count[target] values from Phase 2.

Why this works: Each valid tuple (i, j, k, l) is counted exactly once — when we process the pair (k, l) in Phase 2 and find the pair sum nums1[i] + nums2[j] in the map.

Visual Dry Run#

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

Phase 1 — Build ab_count:

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

Phase 2 — Query for each (k, l):

Total = 1+1+0+0 = 2.

Solution (Optimal)#

from collections import Counter
 
def fourSumCount(nums1: list[int], nums2: list[int],
                 nums3: list[int], nums4: list[int]) -> int:
    # Phase 1: Count all pair sums from nums1 and nums2
    ab_count = Counter(a + b for a in nums1 for b in nums2)
 
    # Phase 2: For each pair from nums3 and nums4, look up the complement
    return sum(ab_count[-(c + d)] for c in nums3 for d in nums4)

var fourSumCount = function(nums1, nums2, nums3, nums4) {
    const abCount = new Map();
 
    // Phase 1: Build frequency map of all pair sums from nums1, nums2
    for (const a of nums1) {
        for (const b of nums2) {
            const sum = a + b;
            abCount.set(sum, (abCount.get(sum) || 0) + 1);
        }
    }
 
    // Phase 2: For each pair from nums3, nums4, count complement matches
    let ans = 0;
    for (const c of nums3) {
        for (const d of nums4) {
            ans += abCount.get(-(c + d)) || 0;
        }
    }
 
    return ans;
};

Time: O(n^2) — O(n^2) to build the map, O(n^2) to query it. Space: O(n^2) — the map can hold up to n^2 distinct sums.

Common Mistakes#

• Enumerating all four arrays: O(n^4) is 1.6 billion operations for n=200 — will time out. The 2+2 split is essential.
• Wrong split (3+1 instead of 2+2): A 3+1 split gives O(n^3) for the first phase — still too slow. Always split as evenly as possible.
• Storing ab_count[sum] = 1 instead of incrementing: Duplicates are undercounted. Use += 1 or Counter.
• Forgetting that the same value combination can produce multiple tuples: If both (a=1,b=-2) and (a=0,b=-1) give sum -1, the frequency of -1 is 2, contributing to different valid tuples.
• Integer overflow in C++: Values up to 2^28 mean pair sums can reach 2^29. Use long long in C++. In Python, no issue.

Interview Tips#

• State the meet-in-the-middle insight before writing any code.
• Explain why the 2+2 split gives O(n^2) while a 3+1 split only gives O(n^3).
• Note that no deduplication is needed here unlike in "4Sum" (LC 18) — every distinct index tuple counts separately.
• Mention the birthday attack connection — same technique used to break cryptographic hash functions by searching for collisions.

Follow-up Questions#

• How would you solve the original 4Sum problem (LC 18) — unique quadruples from one array? Sort + two pointers on the inner two elements with deduplication.
• Can you extend this to 6Sum with six arrays? Split 3+3: O(n^3) per phase. Or chain two hash maps: build pairs of pairs, then use a second lookup.
• What if you want to find the actual tuples, not just count them? Store the actual pairs in the map, then reconstruct. O(n^2) space for pairs.
• How does meet-in-the-middle apply to the subset sum problem? Split the array in half, enumerate all 2^(n/2) subset sums for each half, sort one half and binary search for complements.
• What is the maximum possible answer? n^4 when all values are 0. For n=200, that is 1.6×10^9.

Key Takeaways#

• 4Sum II (LC 454) reduces O(n^4) to O(n^2) using the meet-in-the-middle technique.
• Split the four arrays into two pairs: compute all n^2 sums for the first pair, then for each sum of the second pair look up its negation.
• Time O(n^2), space O(n^2) — the map can hold up to n^2 distinct pair sums.
• No deduplication is needed: every distinct index tuple (i, j, k, l) counts separately.
• The critical rule: always split as evenly as possible — a 2+2 split gives O(n^2) vs O(n^3) for 3+1.
• This technique generalises: for 2k arrays, a k+k split gives O(n^k) — better than O(n^(2k)) naive enumeration.
• The meet-in-the-middle pattern also appears in subset sum, cryptographic birthday attacks, and approximate nearest-neighbour search.