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


  • 3
    A
    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;
        }
    }
    

  • 0
    P

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


  • 0
    A

    @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


Log in to reply
 

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