4Sum II
The key idea
Split the four arrays into two halves. Precompute the count of every pairwise sum
a + b from the first two arrays into a hash map, then for each pair c + d from the last two arrays look up how many earlier pairs equal -(c + d). This turns an O(n^4) search into two O(n^2) passes.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:
- 0 <= i, j, k, l < n
- nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
Tuples are counted by their index positions, so the same value at different indices counts separately.
Constraints
n == nums1.length == nums2.length == nums3.length == nums4.length1 <= n <= 200-2^28 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 2^28
Examples
Input: nums1=[1,2], nums2=[-2,-1], nums3=[-1,2], nums4=[0,2]
Output: 2
Input: nums1=[0], nums2=[0], nums3=[0], nums4=[0]
Output: 1
Complexity
Time: O(n^2) Space: O(n^2)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Hash Map / Set problems
- Contains DuplicateEASY
- Contains Duplicate IIEASY
- Determine if Two Strings Are CloseMEDIUM
- First Missing PositiveHARD
- Equal Row and Column PairsMEDIUM
- Find the Difference of Two ArraysEASY
- Group AnagramsMEDIUM
- Intersection of Two ArraysEASY
- Isomorphic StringsEASY
- Longest Consecutive SequenceMEDIUM
- Longest PalindromeEASY
- Majority Element IIMEDIUM