454-4sum-ii¶

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

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
-2²⁸ <= nums1[i], nums2[i], nums3[i], nums4[i] <= 2²⁸

Solution(Python)¶

class Solution:
    def fourSumCount(
        self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]
    ) -> int:
        return self.optmizedapproach(nums1, nums2, nums3, nums4)

    """
    cntr = 0
    for all possible pairings (atmost n^4 )
        if condition satisfies:
            cntr+=1
    Time Complexity: O(n^4)
    Space Complexity: O(1)
    """

    def bruteforce(
        self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]
    ) -> int:
        n = len(nums1)
        cntr = 0
        for i in range(n):
            for j in range(n):
                for k in range(n):
                    for l in range(n):
                        if nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0:
                            cntr += 1

        return cntr

    """
    cntr = 0
    put -num4 frequency in hashmap
    
    for 3 loops with i,j,k
        if num2+num3+num4 in hashmap:
            cntr+=hashmap[num2+num3+num4]
    Time Complexity: O(n^3)
    Space Complexity: O(n)
    """

    def optmizedbruteforce(
        self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]
    ) -> int:
        n = len(nums1)
        cntr = 0
        hashmap = {}
        for num1 in nums1:
            if -num1 not in hashmap:
                hashmap[-num1] = 1
            else:
                hashmap[-num1] += 1

        for j in range(n):
            for k in range(n):
                for l in range(n):
                    if nums2[j] + nums3[k] + nums4[l] in hashmap:
                        cntr += hashmap[nums2[j] + nums3[k] + nums4[l]]

        return cntr

    """
    cntr = 0
    put -num1-num2 frequency in hashmap
    
    for 2 loops with k,l
        if num3 + num4 in hashmap:
            cntr+=hashmap[num3 + num4]
            
            
    Time Complexity: O(n^2)
    Space Complexity: O(n)
    """

    def optmizedapproach(
        self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]
    ) -> int:
        n = len(nums1)
        cntr = 0
        hashmap = {}
        for num1 in nums1:
            for num2 in nums2:
                if -num1 - num2 not in hashmap:
                    hashmap[-num1 - num2] = 1
                else:
                    hashmap[-num1 - num2] += 1

        for k in range(n):
            for l in range(n):
                if nums3[k] + nums4[l] in hashmap:
                    cntr += hashmap[nums3[k] + nums4[l]]

        return cntr