4Sum II [Medium] — Split and Hash

Problem Statement

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

Input: A=[1,2], B=[-2,-1], C=[-1,2], D=[0,2] → Output: 2

Intuition

Split into two halves. Store all A[i]+B[j] sums in a HashMap with counts. For each C[k]+D[l], check if -(C[k]+D[l]) exists in the map.

Solutions

C++

int fourSumCount(vector<int>& A,vector<int>& B,vector<int>& C,vector<int>& D) {
    unordered_map<int,int> cnt;
    for(int a:A) for(int b:B) cnt[a+b]++;
    int ans=0;
    for(int c:C) for(int d:D) ans+=cnt[-(c+d)];
    return ans;
}

Java

public int fourSumCount(int[] A,int[] B,int[] C,int[] D) {
    Map<Integer,Integer> cnt=new HashMap<>();
    for(int a:A) for(int b:B) cnt.merge(a+b,1,Integer::sum);
    int ans=0;
    for(int c:C) for(int d:D) ans+=cnt.getOrDefault(-(c+d),0);
    return ans;
}

Python

from collections import Counter

def fourSumCount(A, B, C, D):
    ab = Counter(a+b for a in A for b in B)
    return sum(ab[-(c+d)] for c in C for d in D)

JavaScript

var fourSumCount = function(A,B,C,D) {
    const cnt=new Map();
    for(const a of A) for(const b of B) cnt.set(a+b,(cnt.get(a+b)||0)+1);
    let ans=0;
    for(const c of C) for(const d of D) ans+=(cnt.get(-(c+d))||0);
    return ans;
};

Complexity

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