4Sum II — Split-and-Hash for Quadruple Counting

Problem Statement#

Given four integer arrays of equal length n, count tuples (i, j, k, l) such that nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0.

Constraints:

• 1 <= n <= 200
• -2^28 <= nums[i] <= 2^28

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

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

Why This Problem Matters#

LeetCode 454 is the classic meet-in-the-middle interview problem. While not strictly a two-pointer problem, it sits in the broader two-pointer family because the technique — splitting a search space and hashing the halves — is used by many two-pointer follow-ups.

Google, Amazon, and Bloomberg ask it because it tests whether candidates recognize that O(n^4) is too expensive when n hits 200 (1.6 billion operations) but O(n^2) is comfortable. The problem is a gentle introduction to optimization through partitioning.

It also teaches you to count tuples, not just detect existence — a frequent extension in real interview rounds.

The Core Insight#

A naive solution iterates over all four arrays in O(n^4). Instead split the arrays into two pairs: (A, B) and (C, D). Compute every sum a + b and store its frequency in a HashMap. Then for every c + d, look up -(c + d) in the map and add its count to the answer.

The total work is O(n^2) for the first pass and O(n^2) for the second pass — quadratic instead of quartic. Memory is O(n^2) for the HashMap. This trade is worth it because n is small enough that 200^2 = 40000 pairs fit easily.

The algorithm generalizes: any "find/count k-tuples summing to S across k arrays" becomes O(n^(k/2)) via meet-in-the-middle.

Visual Dry Run#

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

Pair sums for A+B: 1+-2=-1, 1+-1=0, 2+-2=0, 2+-1=1. Map of A+B sums: -1 to 1, 0 to 2, 1 to 1.

Pair sums for C+D: -1+0=-1, -1+2=1, 2+0=2, 2+2=4. Look up the negation of each.

Final answer: 2.

Solution (Optimal)#

class Solution:
    def fourSumCount(self, nums1, nums2, nums3, nums4):
        ab = {}
        for a in nums1:
            for b in nums2:
                s = a + b
                ab[s] = ab.get(s, 0) + 1
 
        count = 0
        for c in nums3:
            for d in nums4:
                count += ab.get(-(c + d), 0)
 
        return count

var fourSumCount = function (nums1, nums2, nums3, nums4) {
    const ab = new Map();
    for (const a of nums1) {
        for (const b of nums2) {
            const s = a + b;
            ab.set(s, (ab.get(s) || 0) + 1);
        }
    }
 
    let count = 0;
    for (const c of nums3) {
        for (const d of nums4) {
            count += ab.get(-(c + d)) || 0;
        }
    }
 
    return count;
};

Time: O(n^2) — two nested double loops. Space: O(n^2) — HashMap can hold up to n^2 distinct sums.

Common Mistakes#

• Iterating over all four arrays in O(n^4). Times out for n = 200.
• Storing only existence in the HashMap instead of frequency. You will undercount tuples.
• Using a Set instead of a HashMap. Same bug — frequency lost.
• Forgetting to negate c + d when looking it up.
• Trying to deduplicate quadruples. The problem counts tuples by index, so duplicates are intentional.

Interview Tips#

• State complexity targets up front: "I want O(n^2) time and O(n^2) space."
• Explain meet-in-the-middle as "split, hash one half, scan the other."
• Walk through the example in the dry run — interviewers love when you trace tuples.
• Mention the symmetric pairing (A, B) + (C, D) versus (A, C) + (B, D). Both work.
• Generalize to k-Sum II at the end if asked.

Follow-up Questions#

• How does this generalize to k-Sum II for any k? Hint: O(n^(k/2)) via the same technique.
• Memory limited to O(n). Hint: more elaborate two-pointer schemes per pair, but worse runtime.
• Same problem with up to 10^5 elements. Hint: revisit constraints; the algorithm fundamentally changes.
• Return the tuples themselves, not the count. Hint: store full tuples in the map; memory blows up.
• Different target instead of zero. Hint: look up target - (c + d) instead.

Key Takeaways#

• LeetCode 454 counts quadruples summing to zero across four arrays.
• Meet-in-the-middle: split arrays into two pairs, hash pair sums, scan the other pair.
• Time O(n^2), space O(n^2).
• HashMap must store frequencies, not just existence, because we count tuples.
• Generalizes to k-Sum II in O(n^(k/2)).
• Asked at Google, Amazon, and Bloomberg in 2024 and 2025 cycles.
• Negate the second-pair sum when looking up the first map.