# Dividing arrays into two parts. Full thinking process from naive(N^4) to effective(N^2) solution

1. The naive solution is to run four loops by iterating all elements and check for (A[i] + B[j] + C[k] + d[h]) == 0. Time complexity: N^4
2. We can improve solution by iterating through elements of three arrays and check if the fourth array contains A[i] + B[j] + C[k] + d == 0 ----> d = -A[i] - B[j] - C[k]. We can use HashSet to store elements of fourth array. Overall time complexity: N^3;
3. To improve the solution we can divide arrays into two parts. Then make calculation of sums of one part (A[i] + B[j]) and store their sum's occurences counter in a HashMap. While calculating second part arrays' sum (secondSum = C[k] + D[h]) we can check whether map contains secondSum*(-1);
A[i] + B[j] == - C[k] - D[h]
A[i] + B[j] == - (C[k]+D[h])

This solution can be extended for N arrays.

``````public class Solution {
public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
HashMap<Integer, Integer> sumCounter = getSumCounters(A,B);
int fourSumCounter = 0;
for (int c : C) {
for (int d: D) {
fourSumCounter += sumCounter.getOrDefault(c+d, 0);
}
}
return fourSumCounter;
}

private HashMap<Integer, Integer> getSumCounters(int [] A, int [] B) {
HashMap<Integer, Integer> sumCounter = new HashMap<>();
for (int a : A) {
for (int b: B) {
int sum = -a-b;
sumCounter.put(sum, sumCounter.getOrDefault(sum, 0) + 1);
}
}
return sumCounter;
}
}
``````

• @amanchik How the solution can be extended for N arrays?

• @pernekhan We can calculate sums counter for (n+1)/2 arrays. For the rest of arrays we can run through all elements for (x = n - (n+1)/2; m^x; m is length of array. and check by using the above technique

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.