# 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(n^{4}),
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(n^{2}), and the space complexity is O(n^{2}).

## 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;
}