4 sum II and K SUm II

XXX. Four Sum Count

Hash Map

Divide and Conquer

Problem Statement:

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

Each array has the same length, and the goal is to optimize the solution for efficiency.

Algorithm:

There are two main approaches to solve the problem:

1. Four Sum with Hash Map (O(n²)):
   • Create a hash map to store sums of all pairs from A and B and their frequencies.
   • Iterate through all pairs of C and D, and for each pair, check if the negated sum exists in the hash map.
   • Accumulate the count by the frequency of the negated sum.
2. K-Sum with Divide and Conquer (Generalized):
   • Divide the problem into two halves, summing subsets of arrays A, B and C, D.
   • Use recursive generation of all possible sums for each half and count matches between the two halves using a hash map.
   • This approach generalizes to more than four arrays.

Complexity:

Four Sum with Hash Map: O(n²) time and O(n²) space.
K-Sum with Divide and Conquer: O(2^(k/2) * n) time and O(2^(k/2)) space for k arrays.

Java Implementations:

// Four Sum Count (Hash Map Approach)
public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
    int count = 0; // Tracks the number of valid tuples
    Map map = new HashMap<>(); // Stores sums of pairs from A and B

    // Calculate all possible sums of pairs in A and B
    for (int a : A)
        for (int b : B) {
            int sum = a + b;
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }

    // Check for negated sums using pairs in C and D
    for (int c : C)
        for (int d : D) {
            int sum = c + d;
            if (map.containsKey(-sum)) count += map.get(-sum);
        }

    return count;
}

// K-Sum Count (Generalized Approach)
private int[][] lsts; // Stores input arrays

public int kSumCount(int[] A, int[] B, int[] C, int[] D) {
    lsts = new int[][] { A, B, C, D }; // Combine arrays into a 2D array
    int k = lsts.length; // Number of arrays

    // Calculate sums for the left and right halves
    Map left = sumCount(0, k / 2);
    Map right = sumCount(k / 2, k);

    int res = 0; // Tracks the number of valid tuples

    // Match sums from left and right halves
    for (int s : left.keySet())
        res += left.get(s) * right.getOrDefault(-s, 0);

    return res;
}

// Helper function to calculate all possible sums for a range of arrays
private Map sumCount(int start, int end) {
    Map cnt = new HashMap<>();
    cnt.put(0, 1); // Base case: one way to achieve sum 0

    for (int i = start; i < end; i++) {
        Map map = new HashMap<>();
        for (int a : lsts[i]) {
            for (int total : cnt.keySet()) {
                int newSum = total + a;
                map.put(newSum, map.getOrDefault(newSum, 0) + cnt.get(total));
            }
        }
        cnt = map; // Update with new sums
    }

    return cnt;
}

Explanation:

Four Sum Count (Hash Map Approach):

• Create a hash map for all pairwise sums from A and B along with their frequencies.
• Iterate through all pairs from C and D, and check if the negated sum exists in the hash map.
• For each match, increment the count by the frequency stored in the hash map.

K-Sum Count (Divide and Conquer):

• Divide the arrays into two halves. Compute all possible sums for each half recursively.
• Use a hash map to store sums and their frequencies for the left half.
• For each sum in the right half, check if the negated sum exists in the left half's hash map, and multiply the frequencies.
• This approach generalizes to handle more than four arrays efficiently.