4 Sum II

Published: Jul 9, 2024

Medium Array Hash Table

Problem Description

Given four integer arrays nums1, nums2, nums3, and nums4 all of length n, return the number of tuples (i, j, k, l) such that:

0 <= i, j, k, l < n

nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

Constraints:

n == nums1.length

n == nums2.length

n == nums3.length

n == nums4.length

1 <= n <= 200

-2**28 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 2**28

Examples

Example 1:

Input: nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
Output: 2
Explanation:
The two tuples are:
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

Example 2:

Input: nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
Output: 1

How to Solve

This is a variation of 2 Sum problem. Use a hash table and process two and two arrays. It will be two paths solution. The first loop takes the first and second arrays, and count nums1[i] + nums2[j]. The second loop takes the third and fourth arrays, and find 0 - (nums3[k] + nums4[l]), and count up the value.

class FourSumTwo {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int, int> m;
        for (int n1 : nums1) {
          for (int n2 : nums2) {
            m[n1 + n2]++;
          }
        }
        int count = 0;
        for (int n3 : nums3) {
          for (int n4 : nums4) {
            int target = 0 - (n3 + n4);
            if (m.count(target)) {
              count += m[target];
            }
          }
        }
        return count;
    }
};

class FourSumTwo {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer, Integer> m = new HashMap();
        for (int n1 : nums1) {
          for (int n2 : nums2) {
            m.put(n1 + n2, m.getOrDefault(n1 + n2, 0) + 1);
          }
        }
        int count = 0;
        for (int n3 : nums3) {
          for (int n4 : nums4) {
            count += m.getOrDefault(0 - (n3 + n4), 0);
          }
        }
        return count;
    }
}

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number[]} nums3
 * @param {number[]} nums4
 * @return {number}
 */
var fourSumCount = function(nums1, nums2, nums3, nums4) {
    m  = new Map();
    nums1.forEach((n1) => {
      nums2.forEach((n2) => {
        m.set(n1 + n2, (m.get(n1 + n2) || 0) + 1);
      });
    });
    let count = 0;
    nums3.forEach((n3) => {
      nums4.forEach((n4) => {
        count += (m.get(0 - (n3 + n4)) || 0);
      });
    });
    return count;
};

class FourSumTwo:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        m = defaultdict(int)
        for n1 in nums1:
          for n2 in nums2:
            m[n1 + n2] += 1
        count = 0
        for n3 in nums3:
          for n4 in nums4:
            count += m[0 - (n3 + n4)]
        return count

# @param {Integer[]} nums1
# @param {Integer[]} nums2
# @param {Integer[]} nums3
# @param {Integer[]} nums4
# @return {Integer}
def four_sum_count(nums1, nums2, nums3, nums4)
    m = {}
    nums1.each do |n1|
      nums2.each do |n2|
        m[n1 + n2] = (m[n1 + n2] || 0) + 1;
      end
    end
    count = 0
    nums3.each do |n3|
      nums4.each do |n4|
        count += (m[0 - (n3 + n4)] || 0);
      end
    end
    count
end

Complexities

Time: O(n^2)
Space: O(n^2)