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).
Solutions
Solution
class Solution {public int fourSumCount(int[] A, int[] B, int[] C, int[] D) { int count = 0;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.