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.
- 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.length1 <= n <= 200-100000000 <= values <= 100000000
Hints for 4Sum II
Hint 1
Four nested loops is O(n⁴). Split the four arrays into two halves instead.
Hint 2
Tally every sum
nums1[i] + nums2[j]in a map — that is O(n²) entries.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
- 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 ifngrows.
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 totalJava
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