Coding Interview Patterns4Sum II
MediumHash Maps
4Sum II
Explanation & Solution
Description
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
Input:nums1 = [1, 2], nums2 = [-2, -1], nums3 = [-1, 2], nums4 = [0, 2]
0
1
1
2
0
-2
1
-1
0
-1
1
2
0
0
1
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
Constraints
n == nums1.length == nums2.length == nums3.length == nums4.length1 <= n <= 200-2²⁸ <= nums1[i], nums2[i], nums3[i], nums4[i] <= 2²⁸
Approach
Hash Maps pattern
1. Compute All Pairwise Sums of nums1 and nums2
- Create a hash map
sumMapto store every possible suma + bwhereacomes fromnums1andbcomes fromnums2 - For each sum, record how many pairs produce that sum
2. Check Complementary Sums from nums3 and nums4
- For every pair
(c, d)fromnums3andnums4, computetarget = -(c + d) - Look up
targetin the hash map — if it exists, the value tells us how many(a, b)pairs from step 1 combine with this(c, d)to sum to 0 - Add that count to the running total
3. Return the Total Count
- After iterating through all pairs from
nums3andnums4, the accumulatedcountis the answer
Key Insight
- Splitting the four arrays into two groups of two reduces the problem from O(n⁴) brute force to O(n²)
- We precompute all sums from the first two arrays, then for each sum from the last two arrays we look up the complementary value in O(1)
Time
O(n²)two nested loops of size n, twiceSpace
O(n²)the hash map can store up to n² distinct sumsVisualization
Input:
[1, 2]
—
No animation available
Left (L)Right (R)ConvergedDone
0 steps