Four Sum II Problem
Description
LeetCode Problem 454. Given four lists A, B, C, D of integer values, compute how many quadruplets (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero. All A, B, C, D have same length of N.
Example:
1
2
3
4
5
6
7
8
Input: A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]
Output: 2
Explanation: The two quadruplets 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
Solution
This problem is similar to the four sum problem.
Brute Force Approach
A simple solution is to use the brute force approach.
We loop through each array to get four different elements (a, b, c, d). Then we check whether (a + b + c + d = 0) is true or not.
If it is true, we increase the total count; otherwise, we keep on searching.
The time complexity of this approach is O(n4), and the space complexity is O(1).
Hash Table Approach
We can use the hash table approach similar to the two sum problem to reduce the time complexity.
We first loop through two arrays A and B. During the iteration, we use a hash table to store the sum of the two elements (one from each array) as a key, and the occurrence of such sum as a value.
We then loop through the rest two arrays C and D. We calculate the sum of the two elements (one from each array), and check whether -sum exists in the hash table. If so, we add the number of occurrence of -sum to the total count; otherwise, we continue the searching.
The time complexity can be reduced to O(n2), and the space complexity is O(n2).
Sample C++ Code
This is a C++ implementation of the hash table approach.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
int count = 0;
int len = A.size();
map<int, int> ht;
for (int i = 0; i < len; i ++) {
for (int j = 0; j < len; j ++) {
int x = A[i] + B[j];
if (ht.find(x) == ht.end())
ht[x] = 0;
ht[x] ++;
}
}
for (int i = 0; i < len; i ++) {
for (int j = 0; j < len; j ++) {
int x = -(C[i] + D[j]);
if (ht.find(x) != ht.end())
count += ht[x];
}
}
return count;
}
int main() {
vector<int> A = {1, 2};
vector<int> B = {-2, -1};
vector<int> C = {-1, 2};
vector<int> D = {0, 2};
cout << fourSumCount(A, B, C, D) << endl;
}