# 4Sum II **Difficulty:** MEDIUM [External](https://leetcode.com/problems/4sum-ii) Canonical: https://scaleengineer.com/dsa/problems/4sum-ii **Data structures:** Array, Hash Table --- ## 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` **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 = 0 **Example 2:** **Input:** nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0] **Output:** 1 **Constraints:** * `n == nums1.length` * `n == nums2.length` * `n == nums3.length` * `n == nums4.length` * `1 <= n <= 200` * `-228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228` # Approaches ## Brute Force with Four Nested Loops 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. **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. **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). ### Explanation 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. ```java 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; } } ``` ### Algorithm - 1. Initialize a counter variable `count` to 0. - 2. Use a `for` loop to iterate through `nums1` with index `i`. - 3. Inside, use a nested `for` loop to iterate through `nums2` with index `j`. - 4. Inside, use another nested `for` loop to iterate through `nums3` with index `k`. - 5. Inside, use a final nested `for` loop to iterate through `nums4` with index `l`. - 6. In the innermost loop, check if the sum `nums1[i] + nums2[j] + nums3[k] + nums4[l]` is equal to 0. - 7. If the condition is true, increment the `count`. - 8. After all loops complete, return the final `count`. ## Three Loops with a HashMap 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. **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. **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. ### Explanation First, we create a `HashMap` 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. ```java import java.util.HashMap; import java.util.Map; class Solution { public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) { Map 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; } } ``` ### Algorithm - 1. Create a `HashMap` to store the frequencies of each number in `nums4`. - 2. Iterate through `nums4` and populate the frequency map. For each `num` in `nums4`, update its count in the map. - 3. Initialize a counter `count` to 0. - 4. Use three nested loops to iterate through all combinations of elements from `nums1`, `nums2`, and `nums3`. - 5. For each triplet `(num1, num2, num3)`, calculate their sum `s = num1 + num2 + num3`. - 6. Check if the key `-s` exists in the frequency map. If it does, it means we found a corresponding number in `nums4`. - 7. Add the frequency of `-s` (i.e., `map.get(-s)`) to the `count`. - 8. After the loops complete, return `count`. ## Optimal Two-Pass HashMap (Meet-in-the-Middle) 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. **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. **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. ### Explanation This approach consists of two main parts. First, we pre-compute sums. We create a `HashMap` 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. ```java import java.util.HashMap; import java.util.Map; class Solution { public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) { Map 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; } } ``` ### Algorithm - 1. Create a `HashMap` named `sumFreqMap` to store frequencies of sums. - 2. Use two nested loops to iterate through `nums1` and `nums2`. For each pair `(num1, num2)`, calculate `sum = num1 + num2`. - 3. Store this `sum` and its frequency in `sumFreqMap`. If the sum already exists, increment its count. - 4. Initialize a result counter `count` to 0. - 5. Use another two nested loops to iterate through `nums3` and `nums4`. For each pair `(num3, num4)`, calculate `sum = num3 + num4`. - 6. Determine the `target` sum needed from the first two arrays, which is `-sum`. - 7. Look up this `target` in `sumFreqMap`. If it exists, add its frequency (`sumFreqMap.get(target)`) to `count`. - 8. After all loops complete, return `count`. # Solutions ### Java ```java class Solution { public int fourSumCount(int[] A, int[] B, int[] C, int[] D) { int count = 0; ``` ### Python ```python 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 ``` ### CPP ```cpp // 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 ; } }; ```