4Sum II

Problem Statement

In this problem, you are given four integer arrays: nums1, nums2, nums3, and nums4, each with the same length n. Your task is to determine the number of tuples (i, j, k, l) such that the following conditions are met:

• Each index value (i, j, k, l) is within the range of 0 to n-1.
• The sum of the elements at these indexes from each array equals zero, that is, nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0.

The challenge lies in efficiently counting these tuples given the possible large size of each array (up to 200 elements).

Examples

Example 1

Input:

nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]

Output:

2

Explanation:

The two tuples are:
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

Example 2

Input:

nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]

Output:

1

Constraints

• n == nums1.length
• n == nums2.length
• n == nums3.length
• n == nums4.length
• 1 <= n <= 200
• -228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228

Approach and Intuition

To tackle the problem of finding the tuples where the sum of elements from four different arrays equals zero, we consider the combinatorial nature of the problem and constraints:

1. A direct approach would involve generating all possible tuples (i, j, k, l), computing their sums, and counting how many of those sums equal zero. However, this would result in an O(n^4) time complexity, which is impractical given n can be as large as 200.

2. A more efficient approach utilizes hashing to reduce the time complexity. By noticing that nums1[i] + nums2[j] = -(nums3[k] + nums4[l]), we can separate the problem into two parts:

   • Compute all possible sums of pairs between nums1 and nums2, and store these sums in a hash map, where the key is the sum and the value is the count of how often this sum occurs.
   • Similarly, compute all possible sums of pairs between nums3 and nums4. For each sum, check if the negation of this sum exists in our previously constructed hash map from nums1 and nums2. If it does, it means there are pairs from the first two arrays and pairs from the last two arrays that together sum to zero. The number of such tuples is the product of the occurrences of these sums from the two different parts.

This approach leveraging hash maps allows us to count the qualifying tuples in O(n^2) time, which is a significant improvement over the naïve method. This technique effectively reduces the problem complexity by handling two arrays at a time rather than dealing with all four simultaneously.

Solutions

class Solution {
public:
    int sumOfFour(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        vector<vector<int>> listGroups = {A, B, C, D};
        int n = int(listGroups.size());
    
        auto computeCounts = [&](int startIdx, int endIdx) {
            map<int, int> counts({{0, 1}});
            for (int i = startIdx; i < endIdx; i++) {
                map<int, int> tempCounts;
                for (int element : listGroups[i]) {
                    for (auto it = counts.begin(); it != counts.end(); ++it) {
                        tempCounts[element + it->first] += it->second;
                    }
                }
                counts = tempCounts;
            }
            return counts;
        };
    
        map<int, int> half1Counts = computeCounts(0, n / 2);
        map<int, int> half2Counts = computeCounts(n / 2, n);
        int totalCount = 0;
        for (auto it = half1Counts.begin(); it != half1Counts.end(); ++it) {
            totalCount += it->second * half2Counts[-it->first];
        }
        return totalCount;
    }
};