DEV Community

Abhishek Chaudhary
Abhishek Chaudhary

Posted on

4Sum II

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
  • -228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228

SOLUTION:

class Solution:
    def numTuples(self, k, i, n):
        if (i, k) in self.cache:
            return self.cache[(i, k)]
        if i == n - 1:
            ctr = self.nums[i].count(k)
            self.cache[(i, k)] = ctr
            return ctr
        else:
            ctr = 0
            for num in self.nums[i]:
                ctr += self.numTuples(k - num, i + 1, n)
            self.cache[(i, k)] = ctr
            return ctr

    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        self.cache = {}
        self.nums = [nums1, nums2, nums3, nums4]
        return self.numTuples(0, 0, len(self.nums))
Enter fullscreen mode Exit fullscreen mode

Top comments (0)