4Sum II

Medium
685.

4Sum II

4Sum II is a medium coding problem on arrays, hash table and counting, asked in Amazon, Google and Microsoft interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number[]} nums3
 * @param {number[]} nums4
 * @return {number}
 */
var fourSumCount = function(nums1, nums2, nums3, nums4) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

4Sum II — Solution in Python, Java & C++

4Sum II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon and Google.

4Sum II is a medium coding problem on arrays, hash table and counting, asked in Amazon, Google and Microsoft interviews.

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

Hints for 4Sum II

  1. Hint 1

    Four nested loops is O(n⁴). Split the four arrays into two halves instead.

  2. Hint 2

    Tally every sum nums1[i] + nums2[j] in a map — that is O(n²) entries.

  3. Hint 3

    Then for each nums3[k] + nums4[l], look up its negation and add the tally.

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

  1. Build a map from nums1[i] + nums2[j] to how many (i, j) pairs produce it.
  2. 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

Java

public static int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
    Map<Long, Integer> pair = new HashMap<>();
    for (int a : nums1) {
        for (int b : nums2) {
            long s = (long) a + b;
            pair.put(s, pair.getOrDefault(s, 0) + 1);
        }
    }
    int total = 0;
    for (int c : nums3) {
        for (int d : nums4) {
            total += pair.getOrDefault(-((long) c + d), 0);
        }
    }
    return total;
}

C++

int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
    unordered_map<long long, int> pair;
    for (int a : nums1) {
        for (int b : nums2) pair[(long long) a + b]++;
    }
    int total = 0;
    for (int c : nums3) {
        for (int d : nums4) {
            auto it = pair.find(-((long long) c + d));
            if (it != pair.end()) total += it->second;
        }
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets