Problem Definition

LeetCode: 454. 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

Thought Process

At first glance, this problem might remind you of the classic 3Sum or 4Sum problems, where you search for combinations within a single array that sum to a target. However, there are some critical differences here:

  • We have four separate arrays, and we need to pick one element from each.
  • Unlike the classic 4Sum problem (from a single array), we don’t need to worry about avoiding duplicate quadruples in the same way, because each quadruple is formed from choosing one element from each distinct array. This simplifies the problem substantially.
  • Using a brute force approach—checking all O(n^4) combinations—would be too slow for large n.

Key Insight: We can use a hash map (dictionary) to store the sums of two arrays, and then find complement sums from the other two arrays. Specifically:

  1. Pick two arrays (for instance nums1 and nums2) and compute all possible sums n1 + n2, storing their frequencies in a dictionary. This takes O(n^2) time.
  2. For the remaining two arrays (nums3 and nums4), for each combination n3 + n4, check if -(n3 + n4) is in the dictionary. If it is, we add its frequency to our count.
  3. The dictionary lookups are O(1) on average, so this approach significantly reduces complexity from O(n^4) to O(n^2).

Why Hashing Works Well Here:

  • By precomputing and hashing the sums of nums1 and nums2, we handle half of the problem in O(n^2) time.
  • Then, as we iterate through nums3 and nums4, a single dictionary lookup tells us how many pairs from the first two arrays can complement the current pair to sum to zero.

Solution 1: Using a Dictionary (Hash Map) for Two-Array Sums

How It Works

  1. Create a dictionary (hashmap) to store sums of elements from nums1 and nums2.
    • Key: sum of nums1[i] + nums2[j]
    • Value: count of how many such pairs produce this sum.
  2. Iterate over every pair (n1, n2) in nums1 and nums2, update hashmap[n1+n2] with the frequency.
  3. Initialize a count variable to 0.
  4. For every pair (n3, n4) in nums3 and nums4, compute key = -(n3+n4).
    • If key exists in hashmap, add hashmap[key] to count.
  5. Return count.

Code Explanation

class Solution:
    def fourSumCount(self, nums1, nums2, nums3, nums4):
        # Dictionary to store sum frequencies of nums1 and nums2
        hashmap = dict()
        
        # Compute all sums of elements from nums1 and nums2
        for n1 in nums1:
            for n2 in nums2:
                s = n1 + n2
                hashmap[s] = hashmap.get(s, 0) + 1
        
        # Count how many combinations form zero with nums3 and nums4
        count = 0
        for n3 in nums3:
            for n4 in nums4:
                complement = - (n3 + n4)
                if complement in hashmap:
                    count += hashmap[complement]
                    
        return count

Step-by-Step:

  • Build hashmap for the sums of nums1 and nums2.
  • For each (n3, n4) sum, look up -(n3+n4) in hashmap.
  • Accumulate the count based on frequencies found.

Complexity Analysis

  • Time Complexity: O(n^2), since we generate n^2 pairs from nums1 and nums2, and n^2 pairs from nums3 and nums4.
  • Space Complexity: O(n^2) for the dictionary that stores sums of nums1 and nums2.

Solution 2: Using defaultdict for Cleaner Code

We can simplify dictionary handling further using collections.defaultdict to avoid manual checks.

Code Explanation

from collections import defaultdict

class Solution:
    def fourSumCount(self, nums1, nums2, nums3, nums4):
        rec = defaultdict(int)
        
        # Build frequency map of sums from nums1 and nums2
        for i in nums1:
            for j in nums2:
                rec[i+j] += 1
                
        # Count how many tuples result in zero sum
        count = 0
        for i in nums3:
            for j in nums4:
                count += rec.get(-(i+j), 0)
                
        return count

Step-by-Step:

  • rec is a defaultdict(int), so any new key starts at 0 automatically.
  • Increase rec[i+j] for all combinations from nums1 and nums2.
  • For each (i, j) from nums3 and nums4, add rec[-(i+j)] to count if it exists.

Complexity Analysis:

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

Key Takeaways

  • Hashing Reduces Complexity: Converting a 4-array sum problem from O(n^4) to O(n^2) is achieved by using a hash map to store partial sums.
  • No Need for Complicated Duplicate Removal: Unlike the classic 4Sum problem from a single array, we don’t need to remove duplicates here because each tuple is inherently unique by its four indices chosen from four separate arrays.
  • Scalability: The hashing strategy makes it feasible to handle larger input sizes efficiently.
  • Readability and Pythonic Code: Using defaultdict and get() methods makes the solution concise and clearer.