4Sum II

medium array hash map

Problem

Given four integer arrays A, B, C, D of equal length, return the number of tuples (i, j, k, l) such that A[i] + B[j] + C[k] + D[l] == 0.

InputA=[1,2], B=[-2,-1], C=[-1,2], D=[0,2]

Output2

(0,0,0,1) → 1 + −2 + −1 + 2 = 0; (1,1,0,0) → 2 + −1 + −1 + 0 = 0.

from collections import Counter
def four_sum_count(A, B, C, D):
    ab = Counter()
    for a in A:
        for b in B:
            ab[a + b] += 1
    count = 0
    for c in C:
        for d in D:
            count += ab.get(-(c + d), 0)
    return count

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

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

int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
    unordered_map<int, int> ab;
    for (int a : A) for (int b : B) ab[a + b]++;
    int count = 0;
    for (int c : C) for (int d : D) {
        auto it = ab.find(-(c + d));
        if (it != ab.end()) count += it->second;
    }
    return count;
}

Explanation

We count tuples (i, j, k, l) where A[i] + B[j] + C[k] + D[l] == 0. Checking all four loops at once would be O(n⁴); the trick is to split the four arrays into two halves and meet in the middle with a hash map.

Phase one: compute every pairwise sum a + b from A and B and store how many times each sum occurs in a map ab. That is n² sums recorded.

Phase two: for every pair c + d from C and D, the total is zero exactly when a + b = -(c + d). So we look up ab[-(c + d)] and add however many matches it holds to the running count.

Example: A=[1,2], B=[-2,-1], C=[-1,2], D=[0,2]. The map of A+B sums includes -1, 0, 0, 1. For c+d values, -1 + 2 = 1 needs -1 (one match) and 2 + (-2)?… overall the lookups recover the 2 valid tuples.

By precomputing one side and looking up the complement of the other, the whole thing runs in O(n²) instead of O(n⁴).

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