4Sum II
Problem
Given four integer arrays nums1, nums2, nums3, and nums4 all of length n, return the number of tuples (i, j, k, l) such that nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0.
- n == nums1.length == nums2.length == nums3.length == nums4.length
- 1 ≤ n ≤ 200
- −2²⁸ ≤ nums1[i], nums2[i], nums3[i], nums4[i] ≤ 2²⁸
Example
nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]2The two tuples are: - (0, 0, 0, 1): 1 + (-2) + (-1) + 2 = 0 - (1, 1, 0, 0): 2 + (-1) + (-1) + 0 = 0 A brute-force approach would check all quadruples, which is O(n^4). Instead, the algorithm precomputes sums of pairs from nums1 and nums2, storing their frequencies in a hash map. Then it iterates over pairs from nums3 and nums4, checking if the negated sum exists in the map. This reduces the problem to two nested loops and a hash map lookup, achieving O(n^2) time.
Approach
Straightforward Solution
A brute-force approach enumerates all quadruples (i, j, k, l) and checks if their sum is zero, resulting in O(n^4) time complexity, which is infeasible for n up to 200.
Core Observation
The problem requires counting quadruples where the sum of four elements equals zero. This can be reframed as finding pairs of sums from two arrays that complement pairs of sums from the other two arrays to zero.
Path to Optimal
PreviewBy splitting the problem into two halves, the sums of pairs from nums1 and nums2 can be precomputed and stored in a hash map with their frequencies. Then, for each pair sum from nums3 and nums4, the algorithm checks if the negated sum exists in the map…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewCompute all possible sums of pairs from nums1 and nums2, storing the count of each sum in a hash map. Then iterate over all sums of pairs from nums3 and nums4, and for each sum, check if its negation exists in the hash map…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n^2)
The algorithm computes all pair sums from nums1 and nums2 in O(n^2), and similarly iterates over all pair sums from nums3 and nums4 in O(n^2). Each hash map lookup is O(1) on average, resulting in O(n^2) total time.
Space
O(n^2)
The hash map stores counts of all possible sums of pairs from nums1 and nums2, which can be up to O(n^2) in the worst case. This auxiliary space is necessary to achieve the time complexity improvement.
Pattern Spotlight
Hash Maps (Complement Counting)
When counting tuples across multiple arrays that sum to a target, precompute sums of pairs from half the arrays and store frequencies in a hash map, then check complements from the other half to reduce complexity from exponential to quadratic.
Solution
| 1 | class Solution: |
| 2 | def fourSumCount(self, nums1, nums2, nums3, nums4): |
| 3 | |
| 4 | pair_count = {} |
| 5 | result = 0 |
| 6 | |
| 7 | for a in nums1: |
| 8 | for b in nums2: |
| 9 | pair_sum = a + b |
| 10 | pair_count[pair_sum] = pair_count.get(pair_sum, 0) + 1 |
| 11 | |
| 12 | for c in nums3: |
| 13 | for d in nums4: |
| 14 | target = -(c + d) |
| 15 | if target in pair_count: |
| 16 | result += pair_count[target] |
| 17 | |
| 18 | return result |
Step-by-Step Solution
Build frequency map of sums from nums1 and nums2 pairs
| 4 | pair_count = {} |
| 5 | result = 0 |
| 7 | for a in nums1: |
| 8 | for b in nums2: |
| 9 | pair_sum = a + b |
| 10 | pair_count[pair_sum] = pair_count.get(pair_sum, 0) + 1 |
Objective
To count how many times each possible sum of elements from nums1 and nums2 occurs.
Key Insight
Precomputing sums of pairs from the first two arrays and storing their frequencies in a hash map enables constant-time lookups later. This reduces the problem's complexity by collapsing two nested loops into a single data structure that summarizes all pair sums.
Interview Quick-Check
Core Logic
The hash map stores sums of pairs from nums1 and nums2 as keys and their occurrence counts as values, enabling O(1) complement lookups.
State & Boundaries
Iterate over every element in nums1 and nums2 to cover all pair sums, ensuring completeness.
Common Pitfalls & Bugs
Forgetting to increment the count correctly or initializing counts improperly can lead to incorrect frequency tallies.
Accumulate counts of complementary sums from nums3 and nums4 pairs
To find and sum the counts of pairs from nums3 and nums4 whose negated sums exist in the precomputed hash map.
Return the total count of quadruples summing to zero
To output the final count of all quadruples (i, j, k, l) where the sum of elements equals zero.
2 more steps with full analysis available on Pro.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
pair_count[pair_sum] = pair_count.get(pair_sum, 0) + 1Increment the count of this sum in the hash map.
This line's placement and use of get with default zero ensures accurate frequency counting, which is fundamental to the algorithm's correctness and efficiency.
result += pair_count[target]Add the frequency of the complementary sum to the result.
This line is critical because it aggregates the counts of all valid quadruples, directly contributing to the final answer.
Full line-by-line criticality + rationale for all 12 lines available on Pro.
Test Your Understanding
Why does precomputing sums of pairs from two arrays and using a hash map reduce the problem from O(n^4) to O(n^2)?
See the answer with Pro.
Related Problems
Hash Maps pattern
Don't just read it. Drill it.
Reconstruct 4Sum II from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the 4Sum II drill