We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

4Sum II

Number: 454

Difficulty: Medium

Paid? No

Companies: Google, Adobe

Problem Description

Count the number of quadruplets (i, j, k, l) across four arrays where the sum of nums1[i] + nums2[j] + nums3[k] + nums4[l] equals zero.

Key Insights

  • Use a hash table to store the frequency of all possible sums from nums1 and nums2.
  • For each pair from nums3 and nums4, compute the complement (negative sum) and look it up in the hash table.
  • This reduces the time complexity from O(n^4) to O(n^2).

Space and Time Complexity

Time Complexity: O(n^2) where n is the length of each array. Space Complexity: O(n^2) due to the storage of pair sums in the hash table.

Solution

The solution employs a hash table to precompute and store the frequency of sums of all pairs from the first two arrays. Then, by iterating over all pairs from the third and fourth arrays, we calculate the required complement that would result in a total sum of zero. This complement is checked in the hash table, and the frequency (number of valid pairs) is added to the result. This method efficiently finds the number of valid quadruplets without resorting to a brute-force O(n^4) approach.

Code Solutions

# Function to count quadruplets that sum to zero using a hash map approach
def four_sum_count(nums1, nums2, nums3, nums4):
    # Dictionary to store the frequency of sums of elements from nums1 and nums2
    sum_count = {}
    for num1 in nums1:
        for num2 in nums2:
            current_sum = num1 + num2
            sum_count[current_sum] = sum_count.get(current_sum, 0) + 1

    count = 0
    # For each pair from nums3 and nums4, find the complement that makes the total sum zero
    for num3 in nums3:
        for num4 in nums4:
            complement = -(num3 + num4)
            count += sum_count.get(complement, 0)
    return count

# Example usage
nums1 = [1,2]
nums2 = [-2,-1]
nums3 = [-1,2]
nums4 = [0,2]
print(four_sum_count(nums1, nums2, nums3, nums4))  # Expected Output: 2
← Back to All Questions