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