Problem

Given four lists A, B, C, D of integer values, we want to calculate how many tuples (i, j, k, l) exist such that A[i] + B[j] + C[k] + D[l] equals to zero. All A, B, C, D have same length of N where 0 ≤ N ≤ 500. Also, all the integers in the lists are in the range of -2²⁸ to 2²⁸ - 1 and the result is guaranteed to be at most 2³¹ - 1.

For example:

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

Explanation:

The two tuples that satisfy the condition are:

1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

Approach:

We can solve this problem by using the Hashmap data structure. Hashmap allows us to perform operations like insert and search in constant time. Our approach is to compute possible sums of elements from the first two lists. We will insert these into a hashmap and increment their count. Next, we compute the possible sums of elements from the last two lists. For each such sum, we check if its negative is present in the hashmap (that would mean together they sum up to zero). If yes, it contributes to the result by the count value in the hashmap. By adding these contributions for all sums computed from the last two lists, we get our final answer.

Example:

Let's take a look at an example:

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

Our hashmap after inserting all possible sums from A and B lists, will look like this:

{
-1: 1, 1: 1, 0: 1, }

Then we calculate the sum of the elements of list C and D. When sum is -1, we will check if 1 is in hashmap. If it exists, add its count to the result. Then when sum is 1, we will check if -1 is in hashmap. If it exists, add its count to the result. So our result will be 2.

Solution:

Python

1
2python
3class Solution:
4def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
5        # Store all possible sums from list A and B
6        count = collections.Counter(a + b for a in A for b in B)
7
8        # Calculate sums in list C and D. If the negative sum value exists in count, add its count to the answer.
9        return sum(count[-c - d] for c in C for d in D)

Java

1
2java
3class Solution {
4    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
5        HashMap<Integer, Integer> count = new HashMap<Integer, Integer>();
6
7        for (int a : A)
8            for (int b : B)
9                count.put(a + b, count.getOrDefault(a + b, 0) + 1);
10                
11        int res = 0;
12        for (int c : C)
13            for (int d : D)
14                res += count.getOrDefault(-c - d, 0);
15
16        return res;
17    }
18}

C++

1
2c++
3class Solution {
4public:
5    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
6        unordered_map<int, int> count;
7        int res = 0;
8        
9        for (int a : A)
10            for (int b : B)
11                ++count[a + b];
12                
13        for (int c : C)
14            for (int d : D)
15                res += count[-c - d];
16                
17        return res;
18    }
19};

JavaScript

1
2javascript
3var fourSumCount = function(A, B, C, D) {
4    let count = new Map();
5    let res = 0;
6    
7    for (let a of A)
8        for (let b of B)
9            count.set(a + b, (count.get(a + b) || 0) + 1);
10            
11    for (let c of C)
12        for (let d of D)
13            res += (count.get(-c - d) || 0);
14            
15    return res;
16};

C#

1
2csharp
3public class Solution {
4    public int FourSumCount(int[] A, int[] B, int[] C, int[] D) {
5        Dictionary<int, int> count = new Dictionary<int, int>();
6        int res = 0;
7        
8        foreach (int a in A)
9            foreach (int b in B)
10                if (count.ContainsKey(a + b))
11                    count[a + b]++;
12                else
13                    count[a + b] = 1;
14                
15        foreach (int c in C)
16            foreach (int d in D)
17                if (count.ContainsKey(-c - d))
18                    res += count[-c - d];
19                    
20        return res;
21    }
22}

Complexity Analysis:

The time complexity of the solution is O(N²) because we loop through each pair of elements from each list. The space complexity of the solution is also O(N²) in worst case scenario when all sum values are different and stored in the hashmap.

Conclusion:

This problem can be done efficiently using a Hashmap to store computed sums, reducing the task from a four-array problem to a two array problem. One thing to note is that we're assuming that the insert and search functionality of Hashmap operates in a constant time.

In practical scenarios, it is possible that too many elements lead to a collision in Hashmap which can increase the time complexity. But the chance of this happening is low as the hash function used in programming languages tends to distribute keys uniformly over a wide range.

Hashmaps are a powerful tool and prove extremely helpful in reducing the time complexity of our program by using a bit of extra space. This exact problem can also be solved by using a brute force approach with four nested loops traversing through each list but that would result in a time complexity of O(N^4), which is not feasible for large inputs.

Real world applications of this kind of problem can be found in various areas like four sum problem (finding four elements in an array that sum to a target), database queries, path finding, algorithms in physics simulations etc.