Skip to content

454. 4Sum II

On LeetCode ->

Problem

Given four integer arrays of length \(n\), count the index tuples \((i,j,k,l)\) whose selected values sum to zero.

[1, 2], [-2, -1], [-1, 2], [0, 2] -> 2
Valid index tuples: (0, 0, 0, 1), (1, 1, 0, 0)

Key trick

Use meet-in-the-middle: count every sum from the first two arrays, then add the frequency of the negated sum from the last two arrays.

Trap

  • Counting distinct value combinations instead of index tuples.
  • Storing pair sums in a set, which loses duplicate frequencies.
  • Trying to adapt 4Sum sorting and two pointers, which makes source-array constraints and duplicates difficult to handle.

Why is it interesting?

It turns an \(O(n^4)\) enumeration into \(O(n^2)\) by trading memory for time.

Python solution

class Solution:
    def fourSumCount(
        self,
        nums1: list[int],
        nums2: list[int],
        nums3: list[int],
        nums4: list[int],
    ) -> int:
        # Keep frequencies because equal sums from different index pairs
        # represent different tuples.
        freqs = {}

        for a in nums1:
            for b in nums2:
                s = a + b
                freqs[s] = freqs.get(s, 0) + 1

        cnt = 0

        for c in nums3:
            for d in nums4:
                cnt += freqs.get(-(c + d), 0)

        return cnt

Time complexity: \(O(n^2)\).

Space complexity: \(O(n^2)\).

Comment on my solution

The approach is incomplete and is more complicated than necessary.

  • Several list concatenations are missing +.
  • The second if statement is missing a colon.
  • Some continue statements inside the two-pointer loop do not move either pointer, causing an infinite loop.
  • Merging the arrays forces every candidate to be checked for four distinct source arrays.
  • Two pointers do not directly count duplicate index combinations; incrementing count once can undercount many tuples.
  • The solution does not return count.
  • Dynamic programming and sorting are unnecessary; pair-sum frequencies directly preserve the required multiplicities.
class Solution:
    def fourSumCount(self, nums1: list[int], nums2: list[int], nums3: list[int], nums4: list[int]) -> int:
        #   `0 <= i, j, k, l < n`
        #   `nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0`
        #
        # nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
        # -> 2
        # 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

        # Ideas
        # - use ideas from 3sum problem
        #   - sort numbers so that we can discard tuple and move pointers
        #   - mark a number and use two pointers that move because
        #     of the sum value
        # - maybe DP??

        n = len(nums1)
        count = 0

        nums = ([(x, 1) for x in nums1] +
                [(x, 2) for x in nums2]
                [(x, 3) for x in nums3]
                [(x, 4) for x in nums4])
        nums.sort()

        for i in range(4*n - 3):
            if nums[i][0] > 0:
                continue
            for j in range(i, 4*n - 2):
                # same array
                if nums[i][1] == nums[j][1]:
                    continue
                if nums[i][0] + nums[j][0] > 0:
                    continue
                k = j + 1
                l = 4*n - 1
                while k < l:
                    # not from a distinct array
                    if len(set([nums[i][1], nums[j][1], nums[k][1], nums[l][1]])) != 4:
                        continue
                    s = nums[i][0] + nums[j][0] + nums[k][0] + nums[l][0]

                    if s < 0:
                         k += 1
                    elif s > 0:
                        l -= 1
                    else:
                        count += 1
                        # now we want (i, j - 1) and (i + 1, j)
                        # so we can not move both i and j at the same time