4Sum II
Solve this ProblemTest Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
n == nums1.length == nums2.length == nums3.length == nums4.length - ◆
1 ≤ n ≤ 8 - ◆
-50 ≤ nums1[i], nums2[i], nums3[i], nums4[i] ≤ 50
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Four Nested Loops
GoodTry every possible combination of one index into each array and add the four chosen values up directly, counting how many combinations land on exactly 0. This is the most direct reading of the problem, but checking every quadruple means the work grows with the fourth power of n.
O(n⁴)O(1)1class Solution {
2 public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
3 int n = nums1.length;
4 int count = 0;
5 for (int i = 0; i < n; i++) {
6 for (int j = 0; j < n; j++) {
7 for (int k = 0; k < n; k++) {
8 for (int l = 0; l < n; l++) {
9 if (nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0) {
10 count++;
11 }
12 }
13 }
14 }
15 }
16 return count;
17 }
18}Optimal — HashMap of Pair Sums
OptimalSplit the four arrays into two pairs. Build a hash map counting how often each possible sum a + b occurs across every pair from the first two arrays — that's n² sums stored in O(n²) buckets. Then walk every pair (c, d) from the last two arrays and look up how many pairs from the first half sum to exactly -(c + d); every one of them combines with (c, d) to total zero. Because the lookup is O(1), the whole thing finishes in O(n²) instead of O(n⁴).
O(n²)O(n²)1class Solution {
2 public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
3 Map<Integer, Integer> sumCount = new HashMap<>();
4 for (int a : nums1) {
5 for (int b : nums2) {
6 sumCount.merge(a + b, 1, Integer::sum);
7 }
8 }
9 int count = 0;
10 for (int c : nums3) {
11 for (int d : nums4) {
12 count += sumCount.getOrDefault(-(c + d), 0);
13 }
14 }
15 return count;
16 }
17}