4Sum II — Medium Problem & Solution

Given four integer arrays of the same length n, count the index tuples (i, j, k, l) such that nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0.

Difficulty: Medium
Topics: Arrays, Hash Table, Counting
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given four integer arrays of the same length n, count the index tuples (i, j, k, l) such that nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0.

Tuples are counted by index, so repeated values contribute separately.

Example 1

Input: nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
Output: 2
Explanation: The two valid tuples are (0,0,0,1) and (1,1,0,0).

Example 2

Input: nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
Output: 1

Example 3

Input: nums1 = [1], nums2 = [1], nums3 = [1], nums4 = [1]
Output: 0

Constraints

n == nums1.length == nums2.length == nums3.length == nums4.length
1 <= n <= 200
-100000000 <= values <= 100000000

How to solve 4Sum II

Meet in the middle. The condition a + b + c + d == 0 splits into (a + b) == -(c + d), so precomputing all pairwise sums from the first two arrays turns the search into a lookup.

Approach

Build a map from nums1[i] + nums2[j] to how many (i, j) pairs produce it.
For each (k, l), look up -(nums3[k] + nums4[l]) and add its tally to the answer.

Why it works

Every qualifying tuple is counted exactly once: its first half contributes one unit to the map entry that its second half looks up. Splitting 4 into 2 + 2 takes the cost from n⁴ to n².

Complexity

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

Pitfalls

Looking up nums3[k] + nums4[l] instead of its negation answers a different equation.
A set instead of a count map collapses repeated pair sums and undercounts badly.
The sums reach 200 million, which fits in 32 bits, but the answer can reach n⁴ = 1.6 billion — use 64 bits while accumulating if n grows.

Reference solution

Python

from typing import List

def fourSumCount(nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
    pair = {}
    for a in nums1:
        for b in nums2:
            pair[a + b] = pair.get(a + b, 0) + 1
    total = 0
    for c in nums3:
        for d in nums4:
            total += pair.get(-(c + d), 0)
    return total

JavaScript

var fourSumCount = function(nums1, nums2, nums3, nums4) {
    var pair = {};
    for (var i = 0; i < nums1.length; i++) {
        for (var j = 0; j < nums2.length; j++) {
            var key = String(nums1[i] + nums2[j]);
            pair[key] = (pair[key] === undefined ? 0 : pair[key]) + 1;
        }
    }
    var total = 0;
    for (var k = 0; k < nums3.length; k++) {
        for (var l = 0; l < nums4.length; l++) {
            var want = String(-(nums3[k] + nums4[l]));
            if (pair[want] !== undefined) total += pair[want];
        }
    }
    return total;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue