In this Leetcode 4Sum II problem solution we have given four integer arrays nums1, nums2, nums3, and nums4 all of length n, return the number of tuples (i, j, k, l) such that:

  1. 0 <= i, j, k, l < n
  2. nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

Leetcode 4Sum II problem solution


Problem solution in Python.

from itertools import product
class Solution:
    def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
        def merge(x, y):
            rest = {}
            for i in product(x, y):
                m = sum(i)
                if m in rest: rest[m] += 1
                else: rest[m] = 1
            return rest
        r1 = merge(A, B)
        r2 = merge(C, D)
        rest = 0
        for i1, i2 in product(r1.keys(), r2.keys()):
            m = i1 + i2
            if m == 0:
                rest += r1[i1] * r2[i2]
        return rest



Problem solution in Java.

class Solution {
public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {

    int count=0;
 
    
    HashMap<Integer,Integer> map=new HashMap<>();
    
    for(int i=0;i<A.length;i++){
        for(int j=0;j<B.length;j++){
            
            int sum=A[i]+B[j];
            
            map.put(sum, map.getOrDefault(sum,0)+1);
        }
    }
    
    for(int i=0;i<C.length;i++){
        for(int j=0;j<D.length;j++){
            
            int sum=C[i]+D[j];
            
            if(map.containsKey(-1*sum)){
                
                count+=map.get(-1*sum);
            }
        }
    }
    
    return count;
}
}


Problem solution in C++.

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        int count=0;
        unordered_map<int,int>mp;
        for(int i=0;i<nums1.size();i++){
            for(int j=0;j<nums2.size();j++){
                mp[nums1[i]+nums2[j]]++;
            }
        }
      
        for(int k=0;k<nums3.size();k++){
            for(int l=0;l<nums4.size();l++){
                count+=mp[-(nums3[k]+nums4[l])];
            }
        }
      
        return count;
    }
};