Code Implementation

from collections import Counter

class Solution:
    def fourSumCount(self, A, B, C, D):
        ab_sum = Counter()
        for a in A:
            for b in B:
                ab_sum[a + b] += 1

        count = 0
        for c in C:
            for d in D:
                target = -(c + d)
                count += ab_sum.get(target, 0)
        return count
      

#include <unordered_map>
#include <vector>
using namespace std;

class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        unordered_map<int, int> ab_sum;
        for (int a : A) {
            for (int b : B) {
                ab_sum[a + b]++;
            }
        }
        int count = 0;
        for (int c : C) {
            for (int d : D) {
                int target = -(c + d);
                if (ab_sum.count(target)) {
                    count += ab_sum[target];
                }
            }
        }
        return count;
    }
};
      

import java.util.HashMap;

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

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

Problem Description

The 4Sum II problem asks you to count the number of quadruplets (one element from each of four integer arrays) whose sum is zero.

Given four integer arrays A, B, C, and D of length n, compute how many tuples (i, j, k, l) exist such that:
A[i] + B[j] + C[k] + D[l] == 0

Constraints:

• Each array has the same length n (1 ≤ n ≤ 500).
• All elements are 32-bit signed integers.
• You may use any element as many times as needed (no restriction on reusing values/indices across arrays).

Thought Process

The most direct way to solve this problem is to check every possible quadruplet by looping through all indices i, j, k, and l. However, this brute-force approach means n^4 total combinations, which is computationally infeasible for n = 500.

To optimize, we look for ways to reduce the number of combinations we need to check. Notice that the sum can be split into two parts:
(A[i] + B[j]) + (C[k] + D[l]) == 0
If we know all possible sums of A[i] + B[j] and all possible sums of C[k] + D[l], we can look for pairs that add up to zero.

By using a hash map to store the frequencies of sums from the first two arrays, we can efficiently count how many ways the remaining two arrays can "complete" the sum to zero. This is a classic example of using space (hash map) to save time.

Solution Approach

Here’s a step-by-step breakdown of the optimized solution:

1. Compute all possible sums of A[i] + B[j]:
   • Loop through every element in A and B.
   • For each sum, store the count (frequency) in a hash map. The key is the sum, and the value is how many times it occurs.
2. Iterate over all possible sums of C[k] + D[l]:
   • For each pair, compute the sum.
   • Calculate the complement needed to reach zero: -(C[k] + D[l]).
   • Look up this complement in the hash map from step 1. If it exists, add its frequency to the result count.
3. Return the total count of all such quadruplets.

Why use a hash map? Hash maps provide constant-time lookup and allow us to efficiently count how many ways the first two arrays can contribute to a sum that can be "completed" by the second two arrays.

Example Walkthrough

Let’s walk through an example with small arrays:
A = [1, 2]
B = [-2, -1]
C = [-1, 2]
D = [0, 2]

Step 1: Compute all A[i] + B[j] sums and their frequencies:

• 1 + (-2) = -1
• 1 + (-1) = 0
• 2 + (-2) = 0
• 2 + (-1) = 1

The hash map is: {-1: 1, 0: 2, 1: 1}

• -1 + 0 = -1 → complement = 1 → hash map has 1 occurrence
• -1 + 2 = 1 → complement = -1 → hash map has 1 occurrence
• 2 + 0 = 2 → complement = -2 → hash map has 0 occurrences
• 2 + 2 = 4 → complement = -4 → hash map has 0 occurrences

Total quadruplets: 1 (from -1+0) + 1 (from -1+2) = 2

Time and Space Complexity

Brute-force approach:

• Checks every quadruplet: O(n⁴) time.
• Only needs O(1) extra space.
• Completely impractical for n = 500 (would require 6.25 * 10¹⁰ iterations).

• Computes all A[i] + B[j] sums: O(n²) time.
• Computes all C[k] + D[l] sums and looks up complements: O(n²) time.
• Total time: O(n²) + O(n²) = O(n²).
• Space: O(n²) for the hash map storing all possible A[i] + B[j] sums.

This makes the problem tractable even for the largest input sizes allowed by the constraints.

Summary

The key insight for 4Sum II is to split the four-array sum into two pairs, use a hash map to store the sums of the first pair, and efficiently count complements from the second pair. This reduces an otherwise intractable O(n⁴) problem to a much more efficient O(n²) solution, making it feasible for large inputs. The approach is elegant because it leverages hash maps for fast lookup and counting, turning a brute-force search into a clever, scalable algorithm.