#454

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

4Sum II

Count all quadruples from four integer arrays that sum to zero using efficient array scanning and hash table lookups.

Problem Statement

Given four integer arrays nums1, nums2, nums3, and nums4 each of length n, determine the number of quadruples (i, j, k, l) such that nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0. Each array may contain negative, zero, or positive integers, and tuples can use the same indices from different arrays.

Return the total count of such tuples. For example, given nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2], the result is 2 because two quadruples satisfy the sum condition.

Examples

Example 1

Input: nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]

Output: 2

The two tuples are:

(0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
(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

Example details omitted.

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 Approach

Use a hash map for the first two arrays

Compute all possible sums of elements from nums1 and nums2 and store their frequencies in a hash map. This allows O(1) lookups for any complementary sum needed from the remaining arrays, reducing repeated computation.

Iterate over the last two arrays for complements

For each pair sum from nums3 and nums4, check if the negated sum exists in the hash map. Add the frequency count to the total result to accumulate all valid quadruples efficiently.

Return the total count

After processing all pairs from the last two arrays, the accumulated count in the result variable represents the number of quadruples summing to zero. This completes the solution in O(n^2) time with O(n^2) extra space.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n^2) for computing pair sums and lookups, instead of O(n^4). Space complexity is O(n^2) to store hash map frequencies of the first two arrays' sums.

What Interviewers Usually Probe

Mentions using pair sums to reduce brute-force iterations.
Checks if candidates from remaining arrays complement existing sums.
Looks for efficient O(n^2) approach instead of O(n^4).

Common Pitfalls or Variants

Common pitfalls

Forgetting negative values when computing complements leads to wrong counts.
Double-counting pairs by not using hash map frequencies correctly.
Attempting a naive four-loop approach causing TLE for larger n.

Follow-up variants

Three-sum or k-sum problems with similar pair-sum hash patterns.
Finding tuples with product equal to a target instead of sum.
Using sorted arrays with two-pointer approaches instead of hash maps.

FAQ

What is the main pattern used in 4Sum II?

The main pattern is array scanning combined with hash map lookups to store partial sums for efficient complement checks.

Why not use four nested loops for this problem?

Four nested loops have O(n^4) time complexity, which is inefficient. Using pair sums and hash lookups reduces it to O(n^2).

How do hash maps help in counting quadruples?

They store frequencies of sums from the first two arrays, allowing constant-time checks for complementary sums from the last two arrays.

Can this method be extended to k-sum problems?

Yes, the hash map pair-sum strategy generalizes to k-sum by splitting arrays and storing partial sums efficiently.

What common mistake occurs with negative numbers?

Forgetting to negate the second pair sum when checking the hash map can cause incorrect counts of valid quadruples.

terminal

Solution

Solution 1: Hash Table

We can add the elements $a$ and $b$ in arrays $nums1$ and $nums2$ respectively, and store all possible sums in a hash table $cnt$, where the key is the sum of the two numbers, and the value is the count of the sum.

1

2

3

4

5

6

class Solution:
    def fourSumCount(
        self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]
    ) -> int:
        cnt = Counter(a + b for a in nums1 for b in nums2)
        return sum(cnt[-(c + d)] for c in nums3 for d in nums4)

Continue Practicing

#457 circular array loop #448 find all numbers disappeared in an array #447 number of boomerangs