3.25 4Sum II

3.25.1 Problem Metadata

3.25.2 Description

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

Note: This problem is part of the N Sum Family pattern. See the comparison table in the chapter introduction for a comprehensive comparison of all Two Sum, Three Sum, and Four Sum variants. This multi-array variant uses hash map pair-sum caching instead of sorting.

3.25.3 Examples

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

Output: 2
Explanation:
(i,j,k,l) = (0,0,0,1) and (1,1,0,0) satisfy the equation.

3.25.4 Constraints

  • 0 <= n <= 500
  • -2^28 <= A[i], B[i], C[i], D[i] <= 2^28 - 1
  • Answer fits in a 32-bit signed integer

3.25.5 Solution - Hash Map Pair Sums

3.25.5.1 Walkthrough

Rearrange the equation to (A[i] + B[j]) = -(C[k] + D[l]). Precompute all pair sums of A and B and store their frequencies in a hash map. Then iterate over all pairs in C and D, look up the negated sum in the map, and accumulate the counts.

3.25.5.2 Analysis

  • Time Complexity: O(n�)
  • Space Complexity: O(n�) for storing pair sums

3.25.5.3 Implementation Steps

  1. Iterate over all pairs (i, j) of A and B:
    • Compute sum = A[i] + B[j].
    • Increment map[sum].
  2. For every pair (k, l) of C and D:
    • Compute sum = -(C[k] + D[l]).
    • If sum exists in the map, add map[sum] to the answer.
  3. Return the accumulated total.

3.25.5.4 Code - Java

public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
    Map<Integer, Integer> countMap = new HashMap<>();

    for (int a : A) {
        for (int b : B) {
            int sum = a + b;
            countMap.put(sum, countMap.getOrDefault(sum, 0) + 1);
        }
    }

    int result = 0;
    for (int c : C) {
        for (int d : D) {
            int needed = -(c + d);
            result += countMap.getOrDefault(needed, 0);
        }
    }

    return result;
}