Problem 38.4 · Advanced Search and Divide & ConquerMedium

4Sum II

PatternDivide and Conquer Hash Map Lookup (Complement)

What it teaches: Meet in the middle with a hash map: pair sums of two arrays against pair sums of the other two.

Practise it on judges as “4Sum II”.

In plain words

Four bags of numbers; pick one from each so the four add up to 0. Trying every combination is slow. Instead, write down every sum you can make from the first two bags (and how often). Then for each sum from the last two bags, look up how many first-half sums cancel it out.

Return how many picks add up to 0. Example: [1,2], [-2,-1], [-1,2], [0,2] → 2.

The problem

Count tuples (i, j, k, l) with nums1[i] + nums2[j] + nums3[k] + nums4[l] = 0.

Example 1

Input: [1,2], [-2,-1], [-1,2], [0,2]
Output: 2

Constraints

1 ≤ n ≤ 200 (each array)

Pattern clues in the wording

→ Four lists, one choice from each

These clues point to Divide and Conquer: Split the input into halves, solve each half recursively, and combine the results.

Stuck? Take one hint at a time

Solution · starter

import java.util.*;

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        return 0;
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	nums1 = [1,2] nums2 = [-2,-1] nums3 = [-1,2] nums4 = [0,2]	2
2	nums1 = [0] nums2 = [0] nums3 = [0] nums4 = [0]	1

From slow to fast

Approaches

1. Two halves with a hash map · O(n²)

Two halves with a hash map

Time O(n²) Space O(n²)

count[a + b] over nums1 × nums2; for each c + d, add count[−(c + d)].

▶ Dry run: Meet in the middle with a counternums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]

a + b(list)

1-2 = -11-1 = 02-2 = 02-1 = 1

count(map)

-1: 10: 21: 1

Step 1/3Every sum of one number from nums1 and one from nums2, counted in a map.

Approach 1

import java.util.*;

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int a : nums1) for (int b : nums2) count.merge(a + b, 1, Integer::sum);
        int total = 0;
        for (int c : nums3) for (int d : nums4) total += count.getOrDefault(-(c + d), 0);
        return total;
    }
}

Verdict: The meet-in-the-middle idea in its simplest form.

Before you submit

Edge cases and common mistakes

Test these inputs

All zeros
No solution

Mistakes people make

Three nested loops plus a lookup (O(n³)).

Interview

Follow-up questions

What about k arrays?

Command Palette

The problem

Approaches

Two halves with a hash map

Edge cases and common mistakes

Follow-up questions