medium

4Sum II

Count quadruples across four arrays whose sums add up to zero.

1. Define the problem

4Sum II

Given four integer arrays nums1, nums2, nums3, and nums4, all of the same length n, count how many tuples (i, j, k, l) satisfy nums1i + nums2j + nums3k + nums4l == 0. Instead of checking every combination directly, precompute every possible pairwise sum of nums1 and nums2 in a hash map, then for every pair from nums3 and nums4, look up how many earlier pairs would cancel it out to exactly zero.

Constraints

  • n == nums1.length == nums2.length == nums3.length == nums4.length
  • 1 ≤ n ≤ 200
  • -228 ≤ nums1i, nums2i, nums3i, nums4i ≤ 228

Example

Inputnums1 = [1, 2], nums2 = [-2, -1], nums3 = [-1, 2], nums4 = [0, 2]
Output2

Explanation Two tuples sum to zero: (0, 0, 0, 1) → 1 + (-2) + (-1) + 2 = 0, and (1, 1, 0, 0) → 2 + (-1) + (-1) + 0 = 0.

2. Know the words first

In plain terms

Tuples (i, j, k, l)
One index picked from each of the four arrays — i from the first, j from the second, and so on — combined into a single group of four values.
3. Visualize the solution

The row is the map of nums1+nums2 sums and how often each one appears

The row is the map of nums1+nums2 sums and how often each one appears
Statusbuild-map

Pair nums1[0]=1 with every value in nums2: 1+(-2)=-1, 1+(-1)=0. The sum 1 has not appeared yet, so its cell is still blank.

What happens in this step

a = 1
b = -2: sum = -1 → map[-1] = 1
b = -1: sum = 0 → map[0] = 1
Step 1 of 5

Steps to visualize

  1. Each cell is one sum that nums1 + nums2 can produce. The label is the sum, the value is how many times it has come up.
  2. A cell showing — means that sum has not been recorded yet.
  3. Add every value from nums1 to every value from nums2 and store how many times each sum occurs in a hash map.
  4. For every pair of values from nums3 and nums4, compute their sum and figure out what value from the first map would cancel it out to zero.
  5. Look up that complement in the map and add its count onto the running total.
  6. Once every nums3/nums4 pair has been checked, the running total is the answer.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

The row is the map of nums1+nums2 sums and how often each one appears
Statusbuild-map

Pair nums1[0]=1 with every value in nums2: 1+(-2)=-1, 1+(-1)=0. The sum 1 has not appeared yet, so its cell is still blank.

What happens in this step

a = 1
b = -2: sum = -1 → map[-1] = 1
b = -1: sum = 0 → map[0] = 1
Step 1 of 5
5. Solution

Solution

solution.tsTypeScript
function fourSumCount(nums1, nums2, nums3, nums4) {
  const sumCounts = new Map();

  for (const a of nums1) {
    for (const b of nums2) {
      const sum = a + b;
      sumCounts.set(sum, (sumCounts.get(sum) || 0) + 1);
    }
  }

  let count = 0;

  for (const c of nums3) {
    for (const d of nums4) {
      const complement = -(c + d);
      count += sumCounts.get(complement) || 0;
    }
  }

  return count;
}
Time
O(n^2)
Space
O(n^2)
6. Test cases

Test cases

InputExpectedCovers
nums1 = [1, 2], nums2 = [-2, -1], nums3 = [-1, 2], nums4 = [0, 2]2example from the docstring
nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]1smallest valid input: a single tuple of all zeroes
nums1 = [0, 0], nums2 = [0, 0], nums3 = [0, 0], nums4 = [0, 0]16every array full of zeroes, so every combination sums to zero
nums1 = [1], nums2 = [1], nums3 = [1], nums4 = [1]0no combination of the four arrays can ever sum to zero
nums1 = [-1, -1], nums2 = [-1, 1], nums3 = [-1, 1], nums4 = [1, -1]6a mix of negative and positive values across all four arrays
nums1 = [-1], nums2 = [1], nums3 = [0], nums4 = [0]1a negative and positive value canceling each other out

Keep reading