# 454. 4Sum II (Medium)

https://leetcode.com/problems/4sum-ii/

Given four lists A, B, C, D of integer values, compute how many tuples `(i, j, k, l)` there are such that `A[i] + B[j] + C[k] + D[l]` is zero.

To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most 231 - 1.

Example:

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

Output:
2

Explanation:
The two tuples 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
```

## Solutions

### 1.

``````class Solution {

public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
int count = 0;

// check corner case
if (A == null || A.length == 0) {
return count;
}

int len = A.length;

// Sort four arrays
Arrays.sort(A);
Arrays.sort(B);
Arrays.sort(C);
Arrays.sort(D);

// Fixate array A and B
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {

// Traverse C from left to right
int left = 0;

// Traverse D from right to left
int right = len - 1;

while (left < len && right >= 0) {
// In case of overflow issue
long sum = A[i] * 1l + B[j] * 1l + C[left] * 1l + D[right] * 1l;

// Increase count by 1 once find combination sums up to zero. Meanwhile, move either
// left or right to search for new pairs.
if (sum == 0) {
int cRepeatNum = 1;
int dRepeatNum = 1;

while(left < len - 1 && C[left] == C[left + 1]) {
left++;
cRepeatNum++;
}

while (right > 0 && D[right] == D[right - 1]) {
right--;
dRepeatNum++;
}

left++;
right--;

/*

// forever loop issue

while(left < len - 1 && C[left] == C[++left]) {
cRepeatNum++;
}

while (right > 0 && D[right] == D[--right]) {
dRepeatNum++;
}
*/

count += cRepeatNum * dRepeatNum;

//                            System.out.println(A[i] + ", " + B[j] + ", " + C[left] + ", " + D[right]);

/*
// FIXME Didn't consider situation C=[0, 0, 1], left=0, D=[1,1,1], right=2;

// Imagine that array C has already fully scanned and D still remains a few candidates
// to be visited. As a consequence, we cannot move either left or right randomly which
// is determined by the specific situation.

// In case left pointer has already hit the right boundary. If left pointer gets to
// the right boundary, move right pointer if it is still movable.
if (left == len - 1) {
right--;
} else {
left++;
}
*/
}
// move left pointer to propose larger value such that sum gets close to 0
else if (sum < 0) {
left++;
}
// move right pointer to propose smaller value such that sum gets close to 0
else {
right--;
}
}
}
}

// return ans;
return count;
}
}
``````

### 2.

``````class Solution2 {

// Brute force solution to validate above solution's answer.

public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
// Sort four arrays
Arrays.sort(A);
Arrays.sort(B);
Arrays.sort(C);
Arrays.sort(D);

int len = A.length;
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
for (int m = 0; m < len; m++) {
for (int n = 0; n < len; n++) {
if (A[i] + B[j] + C[m] + D[n] == 0) {
//                                System.out.println(i + ", " + j + ", " + m + ", " + n);
System.out.println(A[i] + ", " + B[j] + ", " + C[m] + ", " + D[n]);
}
}
}
}
}

return 0;
}
}
``````