4Sum II (LeetCode)

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

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

Constraints

• n == nums1.length
• n == nums2.length
• n == nums3.length
• n == nums4.length
• 1 <= n <= 200
• -228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228

Approach

Create an empty map called "mp" to store integer keys and their corresponding counts.

Iterate over each element "k" in the "nuns3" vector.

For each "k", iterate over each element "l" in the "nums4" vector.

Add the sum of "k" and "l" as a key in the map "mp" and increment its count by 1.

Initialize a variable "count" to 0.

Iterate over each element "i" in the "nums1" vector.

For each "i", iterate over each element "j" in the "nums2" vector.

Find the value associated with the key -(i + j) in the map "mp" and add it to the "count".

Return the value of "count" as the result.

Solution Code

C++

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {

        unordered_map<int,int> mp;
        
       
        for(int k : nums3)
            for(int l : nums4)
                mp[k + l]++;
        
       
        int count = 0;
        for(int i : nums1)
            for(int j : nums2)
                count += mp[-(i + j)];
        
        return count;
    }
};

java

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int n1 : nums1) {
            for (int n2 : nums2) {
                map.put(n1 + n2, map.getOrDefault(n1 + n2, 0) + 1);
            }
        }

        int count = 0;
        for (int n3 : nums3) {
            for (int n4 : nums4) {
                count += map.getOrDefault(-(n3 + n4), 0);
            }
        }
        return count;
    }
}

Python

class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        dc1=defaultdict(lambda:0)
        for a in nums1:
            for b in nums2:
                dc1[a+b]+=1
        ans=0
        for c in nums3:
            for d in nums4:
                ans+=dc1[-c-d]
        return ans

Conclusion

• 1. Time complexity:O(n^2)
• 2. Space complexity:O(n^2)