4Sum II

Share

Count tuples (i,j,k,l) such that nums1[i]+nums2[j]+nums3[k]+nums4[l] == 0.

Example 1
Input: nums1=[1,2], nums2=[-2,-1], nums3=[-1,2], nums4=[0,2] → Output: 2
Example 2
Input: nums1=[0], nums2=[0], nums3=[0], nums4=[0] → Output: 1

Solution Approach

Split into two pairs. Map sums of pair1, then look for negation in pair2.

  • HashMap: store count of all a+b sums for nums1 and nums2
  • For each c+d in nums3 and nums4
  • Look up -(c+d) in map and add count to result
  • Return result
Java
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int a : nums1)
        for (int b : nums2)
            map.merge(a + b, 1, Integer::sum);
    int count = 0;
    for (int c : nums3)
        for (int d : nums4)
            count += map.getOrDefault(-(c + d), 0);
    return count;
}
  • Time Complexity: O(n^2)
  • Space Complexity: O(n^2)