O(N^2) time complexity [Accepted]


  • 0
    S

    Given that A[i] + B[j] +C[k] + D[l] = 0, we can say that, A[i] + B[j] = -(C[k] + D[l])
    With this idea, you can compute all the summation pairs of two respective arrays in a HashMap with a count of how many times you incurred that sum. So now you have two HashMaps map1 and map2 with the key as the summation of two elements and value as the number of time you got the summation. You just need to do the summation of map1[key] X map2[key], for all the keys that are present in both map1 and map2.

    class Solution {
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        int n = A.length;
        HashMap<Integer, Integer> map1 = new HashMap<>();
        HashMap<Integer, Integer> map2 = new HashMap<>();
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                map1.put((A[i] + B[j]), map1.getOrDefault((A[i] + B[j]), 0) + 1 );
            }
        }
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(map1.containsKey( -(C[i] + D[j])))
                    map2.put( -(C[i] + D[j]), map2.getOrDefault(-(C[i] + D[j]), 0) + 1 );
            }
        }
        int count = 0;
        for(Integer key: map1.keySet()) {
            if(map2.containsKey(key)) {
                count += map2.get(key) * map1.get(key);
            }
        }
        return count;
    }
    }

Log in to reply
 

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