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 < nnums1[i] + nums2[j] + nums3[k] + nums4[l] == 0Example 1:
Input: nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,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
Example 2:
Input: nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0] Output: 1
Constraints:
n == nums1.lengthn == nums2.lengthn == nums3.lengthn == nums4.length1 <= n <= 200-228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228The key idea in #454 4Sum II is to efficiently count quadruplets across four arrays such that their total sum equals zero. A brute-force approach would check every combination of elements from the four arrays, leading to O(n^4) time complexity, which is impractical for larger inputs.
A more optimal strategy reduces the problem using a hash table. First, compute all possible pair sums from the first two arrays and store their frequencies in a hash map. Next, iterate through all pair sums formed by the remaining two arrays and look for the complementary value that would make the total sum zero.
This transforms the problem into two pair-sum computations instead of four nested loops. By leveraging frequency counts in the hash map, we can quickly determine how many valid combinations exist for each complementary sum. This approach significantly improves efficiency while keeping the logic manageable for interview scenarios.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Brute Force (4 nested loops) | O(n^4) | O(1) |
| Hash Map Pair Sum Optimization | O(n^2) | O(n^2) |
NeetCode
This approach leverages hash maps to efficiently count and use pair sums. First, we compute all possible sums between arrays nums1 and nums2, storing them in a hash map along with their count. Then, we iterate over pairs of nums3 and nums4, checking how many complements (to form a sum of zero) exist in the hash map.
Time Complexity: O(n^2), with each pair calculation taking constant time.
Space Complexity: O(n^2), using space for hash map storage.
1function fourSumCount(nums1, nums2, nums3, nums4) {
2 const sumMap = new Map();
3 let count = 0;
4
5 for (let a of nums1) {
6 for (let b of nums2) {
7 const sum = a + b;
8 sumMap.set(sum, (sumMap.get(sum) || 0) + 1);
9 }
10 }
11
12 for (let c of nums3) {
13 for (let d of nums4) {
14 const complement = -(c + d);
15 if (sumMap.has(complement)) {
16 count += sumMap.get(complement);
17 }
18 }
19 }
20
21 return count;
22}
23The JavaScript implementation employs a Map to keep counts of the sums of elements from nums1 and nums2. It then iterates through possible sums of nums3 and nums4, checking how many can complement each other to form a zero total sum.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of the 4Sum and k-sum problems frequently appear in technical interviews at large tech companies. They test understanding of hash maps, optimization from brute force, and the ability to reduce higher-order problems into simpler subproblems.
The optimal approach uses a hash map to store pair sums from the first two arrays and their frequencies. Then it checks pair sums from the remaining arrays and looks for complementary values that sum to zero. This reduces the time complexity from O(n^4) to O(n^2).
A hash map is the most effective data structure for this problem. It allows fast storage and lookup of pair sums and their counts, enabling efficient matching with complementary sums from the other arrays.
The pair-sum technique reduces the number of nested loops by grouping elements into pairs. Instead of checking four numbers at once, the algorithm compares two pair sums, dramatically improving performance and making the solution scalable.