# 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
1. (0, 0, 0, 1) => A + B + C + D = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) => A + B + C + D = 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;
}
``````