4Sum II
MedPrompt
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] == 0
Example 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 = 0Example 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] <= 228
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward way to solve the problem is to check every possible combination of one element from each of the four arrays. We can use four nested loops to iterate through all tuples (i, j, k, l) and check if the sum of the corresponding elements is zero. If it is, we increment a counter.
Algorithm
-
- Initialize a counter variable
countto 0.
- Initialize a counter variable
-
- Use a
forloop to iterate throughnums1with indexi.
- Use a
-
- Inside, use a nested
forloop to iterate throughnums2with indexj.
- Inside, use a nested
-
- Inside, use another nested
forloop to iterate throughnums3with indexk.
- Inside, use another nested
-
- Inside, use a final nested
forloop to iterate throughnums4with indexl.
- Inside, use a final nested
-
- In the innermost loop, check if the sum
nums1[i] + nums2[j] + nums3[k] + nums4[l]is equal to 0.
- In the innermost loop, check if the sum
-
- If the condition is true, increment the
count.
- If the condition is true, increment the
-
- After all loops complete, return the final
count.
- After all loops complete, return the final
Walkthrough
This approach exhaustively checks every single tuple. We initialize a counter variable, count, to zero. The first loop iterates through nums1, the second through nums2, the third through nums3, and the fourth through nums4. Inside the innermost loop, we calculate the sum of the four selected elements. If this sum equals 0, we increment our count. After all loops have finished, count will hold the total number of valid tuples, which we then return. While simple to conceptualize, this method is computationally expensive and not practical for the given constraints.
class Solution { public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) { int count = 0; int n = nums1.length; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { for (int l = 0; l < n; l++) { if (nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0) { count++; } } } } } return count; }}Complexity
Time
O(n^4), as it involves four nested loops, each running `n` times. For n=200, this is approximately 200^4 = 1.6 * 10^9 operations, which is too slow.
Space
O(1), as we only use a few variables to store the count and loop indices, independent of the input size.
Trade-offs
Pros
Simple to understand and implement.
Requires no extra space (O(1) space complexity).
Cons
Extremely inefficient due to its O(n^4) time complexity.
Guaranteed to result in a 'Time Limit Exceeded' (TLE) error for the given constraints (n <= 200).
We can improve upon the brute-force approach by reducing the number of nested loops from four to three. The core idea is to rearrange the target equation a + b + c + d = 0 to a + b + c = -d. We can pre-process one of the arrays, say nums4, and store the frequency of each of its elements in a HashMap. Then, we iterate through the first three arrays with three nested loops, calculate their sum s, and check how many times -s appears in nums4 using the map.
Algorithm
-
- Create a
HashMapto store the frequencies of each number innums4.
- Create a
-
- Iterate through
nums4and populate the frequency map. For eachnuminnums4, update its count in the map.
- Iterate through
-
- Initialize a counter
countto 0.
- Initialize a counter
-
- Use three nested loops to iterate through all combinations of elements from
nums1,nums2, andnums3.
- Use three nested loops to iterate through all combinations of elements from
-
- For each triplet
(num1, num2, num3), calculate their sums = num1 + num2 + num3.
- For each triplet
-
- Check if the key
-sexists in the frequency map. If it does, it means we found a corresponding number innums4.
- Check if the key
-
- Add the frequency of
-s(i.e.,map.get(-s)) to thecount.
- Add the frequency of
-
- After the loops complete, return
count.
- After the loops complete, return
Walkthrough
First, we create a HashMap<Integer, Integer> to store the frequency of each number in nums4. We iterate through nums4 and for each element, we update its count in the map. Then, we initialize a counter count to 0. We use three nested loops to iterate through all combinations of elements from nums1, nums2, and nums3. For each combination, we calculate their sum sum_abc. We then look for the required fourth element, which would be -sum_abc. We check our frequency map for the key -sum_abc. If the map contains this key, we add its stored frequency to our total count. After iterating through all combinations from the first three arrays, count will hold the final result.
import java.util.HashMap;import java.util.Map; class Solution { public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) { Map<Integer, Integer> freqMap4 = new HashMap<>(); for (int num : nums4) { freqMap4.put(num, freqMap4.getOrDefault(num, 0) + 1); } int count = 0; for (int num1 : nums1) { for (int num2 : nums2) { for (int num3 : nums3) { int sum = num1 + num2 + num3; count += freqMap4.getOrDefault(-sum, 0); } } } return count; }}Complexity
Time
O(n^3). Populating the map takes O(n), and the three nested loops take O(n^3). The dominant term is O(n^3). For n=200, this is 200^3 = 8 * 10^6 operations, which is feasible.
Space
O(n), as the HashMap can store up to `n` distinct elements from `nums4` in the worst case.
Trade-offs
Pros
Significantly faster than the brute-force approach.
Reduces the time complexity from O(n^4) to O(n^3), which is likely to pass the time limits for n=200.
Cons
Requires extra space for the HashMap.
While much better than brute force, it's not the most optimal solution.
The most efficient solution uses a "meet-in-the-middle" strategy. We split the four arrays into two groups: (nums1, nums2) and (nums3, nums4). The equation a + b + c + d = 0 is rearranged to a + b = -(c + d). We first compute all possible sums from the first group (a + b) and store their frequencies in a HashMap. Then, we iterate through the second group, compute their sums (c + d), and for each sum, we check how many times its negation -(c + d) appeared in the HashMap, adding that count to our result.
Algorithm
-
- Create a
HashMap<Integer, Integer>namedsumFreqMapto store frequencies of sums.
- Create a
-
- Use two nested loops to iterate through
nums1andnums2. For each pair(num1, num2), calculatesum = num1 + num2.
- Use two nested loops to iterate through
-
- Store this
sumand its frequency insumFreqMap. If the sum already exists, increment its count.
- Store this
-
- Initialize a result counter
countto 0.
- Initialize a result counter
-
- Use another two nested loops to iterate through
nums3andnums4. For each pair(num3, num4), calculatesum = num3 + num4.
- Use another two nested loops to iterate through
-
- Determine the
targetsum needed from the first two arrays, which is-sum.
- Determine the
-
- Look up this
targetinsumFreqMap. If it exists, add its frequency (sumFreqMap.get(target)) tocount.
- Look up this
-
- After all loops complete, return
count.
- After all loops complete, return
Walkthrough
This approach consists of two main parts. First, we pre-compute sums. We create a HashMap<Integer, Integer> and use two nested loops to iterate through every pair of elements from nums1 and nums2. For each pair, we compute their sum and store it as a key in the map, with its frequency as the value.
Second, we count the tuples. We initialize a counter count to 0. We use another pair of nested loops to iterate through every pair from nums3 and nums4. For each pair, we compute their sum s_cd. The target sum we need from the first two arrays is target = -s_cd. We look up this target in our map. If the key exists, we add its frequency to our count. This works because every time we find a match, it means there are frequency pairs from nums1 and nums2 that, when combined with the current pair from nums3 and nums4, sum to zero.
import java.util.HashMap;import java.util.Map; class Solution { public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) { Map<Integer, Integer> sumFreqMap = new HashMap<>(); // Part 1: Compute sums from nums1 and nums2 and store their frequencies for (int num1 : nums1) { for (int num2 : nums2) { int sum = num1 + num2; sumFreqMap.put(sum, sumFreqMap.getOrDefault(sum, 0) + 1); } } int count = 0; // Part 2: Find complements from nums3 and nums4 for (int num3 : nums3) { for (int num4 : nums4) { int sum = num3 + num4; int target = -sum; count += sumFreqMap.getOrDefault(target, 0); } } return count; }}Complexity
Time
O(n^2). The first part involves two nested loops (O(n^2)) to populate the map. The second part also involves two nested loops (O(n^2)) with a constant time map lookup. The total complexity is O(n^2) + O(n^2) = O(n^2).
Space
O(n^2). In the worst-case scenario, all `n*n` sums from `nums1` and `nums2` are unique, requiring the HashMap to store `n^2` entries. For n=200, this is 40,000 entries, which is manageable.
Trade-offs
Pros
Highly efficient with a time complexity of O(n^2).
This is the standard and optimal approach for this type of k-sum problem.
Cons
Uses O(n^2) extra space, which can be significant if n is very large, though it's acceptable for the given constraints.
Solutions
Solution
class Solution {public int fourSumCount(int[] A, int[] B, int[] C, int[] D) { int count = 0;from collections import Counter 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 ) ############ class Solution : def fourSumCount ( self , nums1 : List [ int ], nums2 : List [ int ], nums3 : List [ int ], nums4 : List [ int ] ) -> int : counter = Counter () for a in nums1 : for b in nums2 : counter [ a + b ] += 1 ans = 0 for c in nums3 : for d in nums4 : # adding for every time -(c+d) ans += counter [ - ( c + d )] return ans ############ class Solution ( object ): def fourSumCount ( self , A , B , C , D ): """ :type A: List[int] :type B: List[int] :type C: List[int] :type D: List[int] :rtype: int """ ans = 0 abDict = {} for i in range ( len ( A )): for j in range ( len ( B )): if A [ i ] + B [ j ] not in abDict : abDict [ A [ i ] + B [ j ]] = 1 else : abDict [ A [ i ] + B [ j ]] += 1 for i in range ( len ( C )): for j in range ( len ( D )): if - C [ i ] - D [ j ] in abDict : ans += abDict [ - C [ i ] - D [ j ]] return ans// OJ: https://leetcode.com/problems/4sum-ii // Time: O(N^2 * logN) // Space: O(N^2) class Solution { private: void sum ( vector < int > & A , vector < int > & B , map < int , int > & m ) { for ( auto a : A ) { for ( auto b : B ) m [ a + b ] ++ ; } } public: int fourSumCount ( vector < int >& A , vector < int >& B , vector < int >& C , vector < int >& D ) { map < int , int > a , b ; sum ( A , B , a ); sum ( C , D , b ); auto i = a . begin (); auto j = b . rbegin (); int ans = 0 ; while ( i != a . end () && j != b . rend ()) { if ( i -> first + j -> first == 0 ) { ans += i -> second * j -> second ; ++ i ; ++ j ; } else if ( i -> first + j -> first < 0 ) ++ i ; else ++ j ; } return ans ; } };Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.