4Sum II — Two-Map Split and Match

Problem 200 · 4Sum II

Difficulty: Medium · Pattern: Two-Map (Meet in Middle)

Given four arrays, count tuples (i,j,k,l) such that A[i]+B[j]+C[k]+D[l] == 0.

Intuition

Compute all pair sums of A+B in a map. Then for each pair C[k]+D[l], check if -(c+d) exists in the map.

Solutions

# Python
from collections import Counter
def fourSumCount(nums1, nums2, nums3, nums4):
    ab = Counter(a+b for a in nums1 for b in nums2)
    return sum(ab[-(c+d)] for c in nums3 for d in nums4)

// Java
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 ans = 0;
    for (int x : c) for (int y : d)
        ans += ab.getOrDefault(-(x+y), 0);
    return ans;
}

// C++
int fourSumCount(vector<int>& a, vector<int>& b, vector<int>& c, vector<int>& d) {
    unordered_map<int,int> ab;
    for (int x : a) for (int y : b) ab[x+y]++;
    int ans = 0;
    for (int x : c) for (int y : d) ans += ab.count(-(x+y)) ? ab[-(x+y)] : 0;
    return ans;
}

// JavaScript
var fourSumCount = function(a, b, c, d) {
    const ab = new Map();
    for (const x of a) for (const y of b) ab.set(x+y, (ab.get(x+y)||0)+1);
    let ans = 0;
    for (const x of c) for (const y of d) ans += ab.get(-(x+y)) || 0;
    return ans;
};

Complexity

Time: O(n²)
Space: O(n²)