Log inSign up
mediumLeetCodeNot Started

4Sum II

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

Given four integer arrays nums1, nums2, nums3, and nums4 all of length n, return the number of tuples (i, j, k, l) such that:

- 0 <= i, j, k, l < n - nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

Example 1:

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

Example 2:

Input: nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
Output: 1
Explanation: The only tuple is (0, 0, 0, 0) which sums to 0.

Constraints:

  • n == nums1.length
  • n == nums2.length
  • n == nums3.length
  • n == nums4.length
  • 1 <= n <= 200
  • -228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Hash Map Lookup and Frequency Counting
  • Meet in the Middle Concept
  • Time-Space Complexity Trade-offs

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the Meet-in-the-Middle partitioning technique to turn an O(N4) problem into O(N2).
  • Understand why 4Sum II allows simple frequency counting without deduplication unlike 4Sum I.
  • Handle 64-bit integer arithmetic considerations when summing large values.
  • Evaluate hash table load factors and sizing for N2 intermediate pairs.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Problem asks to find tuples across 4 distinct arrays summing to 0.
  • Constraints: N <= 200 (N4 = 1.6 * 109 is too slow, N2 = 40,000 is extremely fast).
  • No deduplication of identical values required—only counting valid index tuples.

Algorithmic Decision Tree:

  • Split arrays into two halves: group 1 = (nums1, nums2), group 2 = (nums3, nums4).
  • Compute sum frequencies of group 1 in a Hash Map: countMap[a + b]++.
  • Traverse group 2, for each pair (c, d), look up -(c + d) in countMap.
  • Sum all matched frequencies.

Connected Patterns:

Two Sum (Hash Map complement lookup)4Sum (Sorting + Two Pointers on a single array with deduplication)Meet in the Middle / Subset Sum Partitioning

1. Check All Quadruplets (Brute Force)

Intuition

Iterate with 4 nested loops across arrays of size n: for each a in nums1, b in nums2, c in nums3, d in nums4, check if a + b + c + d == 0. If so, increment count.

When to apply: Use to understand the 4-tuple zero-sum requirement.

Four Nested Loops (O(N^4) Time)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Evaluate first combination out of 2^4 = 16 quadruples
Visual state
Values and pointers at this exact step
hashmap
Input array
S
1
-2
-1
0
0
↑ quad0
1
2
3
Hash map state
Execution state
a1
b-2
c-1
d0
sum-2
count0
Sum != 0. Do not increment count.
Variables at this step
a
1
b
-2
c
-1
d
0
sum
-2
count
0
Check / comparison
Quadruple (1, -2, -1, 0): sum = 1 + (-2) + (-1) + 0 = -2 != 0
Decision / next transition
Sum != 0. Do not increment count.
Why this step matters

Evaluate first combination out of 24 = 16 quadruples.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
4 int count = 0;
5 for (int a : nums1) {
6 for (int b : nums2) {
7 for (int c : nums3) {
8 for (int d : nums4) {
9 if (a + b + c + d == 0) count++;
10 }
11 }
12 }
13 }
14 return count;
15 }
16 }
17
18 public static void main(String[] args) {
19 Solution sol = new Solution();
20 int[] nums1 = {1, 2}, nums2 = {-2, -1}, nums3 = {-1, 2}, nums4 = {0, 2};
21 System.out.println("Tuple count: " + sol.fourSumCount(nums1, nums2, nums3, nums4));
22 }
23}

Time & Space Complexity

  • Time complexity: O(n^4) — Four nested loops over arrays of size n.
  • Space complexity: O(1) — O(1) auxiliary space.

Why Brute Force Doesn't Scale:

At N = 200, N4 exceeds 1.6 billion operations, timing out on modern online judges.

The Meet-in-the-Middle hash map approach performs 40,000 insertions and 40,000 lookups (80,000 operations total), executing in under 30ms.

2. Sort and Binary Search on Fourth Array

Intuition

Sorting nums4 takes O(n log n). For every triplet a in nums1, b in nums2, c in nums3, compute target = -(a + b + c). Count occurrences of target in nums4 using binary search range queries (upper_bound - lower_bound).

When to apply: Use to understand partial search-space reduction.

Split Pairs & Binary Search (O(N^2 log N) Time)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Reducing 4 dimensions into two 2-dimensional sets
Visual state
Values and pointers at this exact step
hashmap
Input array
S
-1
0
0
1
0
↑ AB
1
2
3
Hash map state
Execution state
abSums[-1,0,0,1]
count0
List AB has size N^2 = 4.
Variables at this step
abSums
[-1,0,0,1]
count
0
Check / comparison
Compute all pair sums A[i] + B[j]: [-1, 0, 0, 1]
Decision / next transition
List AB has size N^2 = 4.
Why this step matters

Reducing 4 dimensions into two 2-dimensional sets.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
6 Arrays.sort(nums4);
7 int count = 0;
8
9 for (int a : nums1) {
10 for (int b : nums2) {
11 for (int c : nums3) {
12 int target = -(a + b + c);
13 int first = lowerBound(nums4, target);
14 int last = upperBound(nums4, target);
15 count += (last - first);
16 }
17 }
18 }
19 return count;
20 }
21
22 private int lowerBound(int[] arr, int target) {
23 int l = 0, r = arr.length;
24 while (l < r) {
25 int mid = l + (r - l) / 2;
26 if (arr[mid] >= target) r = mid;
27 else l = mid + 1;
28 }
29 return l;
30 }
31
32 private int upperBound(int[] arr, int target) {
33 int l = 0, r = arr.length;
34 while (l < r) {
35 int mid = l + (r - l) / 2;
36 if (arr[mid] > target) r = mid;
37 else l = mid + 1;
38 }
39 return l;
40 }
41 }
42
43 public static void main(String[] args) {
44 Solution sol = new Solution();
45 int[] nums1 = {1, 2}, nums2 = {-2, -1}, nums3 = {-1, 2}, nums4 = {0, 2};
46 System.out.println("Tuple count: " + sol.fourSumCount(nums1, nums2, nums3, nums4));
47 }
48}

Time & Space Complexity

  • Time complexity: O(n^3 log n) — n3 triplets, each performing binary search.
  • Space complexity: O(1) — O(1) auxiliary space.

3. Hash Map of Pair Sums (Optimal & Standard)

Intuition

1. Create a hash map storing the frequency of all sums (a + b) for a in nums1, b in nums2. 2. For each pair (c, d) in nums3 and nums4, target = -(c + d). 3. If target is in the map, add map[target] to the total count. Combining pairs reduces 4 loops to 2 separate 2-loop passes.

When to apply: Use as the clean StudyVex Gold Standard for 4Sum II.

Hash Map of A+B Sum Frequencies (O(N^2) Time, O(N^2) Space)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Duplicate sum 0 has count 2
Visual state
Values and pointers at this exact step
hashmap
Input array
S
-1
0
0
1
0
↑ AB
1
2
3
Hash map state
3 stored entries
key
-1
maps to index
1
key
0
maps to index
2
key
1
maps to index
1
freqAB: { -1: 1, 0: 2, 1: 1 }.
Variables at this step
map state
-1: 1, 0: 2, 1: 1
count
0
Check / comparison
Enumerate all pair sums A[i] + B[j] and populate hash map
Decision / next transition
freqAB: { -1: 1, 0: 2, 1: 1 }.
Why this step matters

Duplicate sum 0 has count 2.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
6 Map<Integer, Integer> map = new HashMap<>();
7 for (int a : nums1) {
8 for (int b : nums2) {
9 map.put(a + b, map.getOrDefault(a + b, 0) + 1);
10 }
11 }
12
13 int count = 0;
14 for (int c : nums3) {
15 for (int d : nums4) {
16 int target = -(c + d);
17 count += map.getOrDefault(target, 0);
18 }
19 }
20 return count;
21 }
22 }
23
24 public static void main(String[] args) {
25 Solution sol = new Solution();
26 int[] nums1 = {1, 2}, nums2 = {-2, -1}, nums3 = {-1, 2}, nums4 = {0, 2};
27 System.out.println("Tuple count: " + sol.fourSumCount(nums1, nums2, nums3, nums4));
28 }
29}

Time & Space Complexity

  • Time complexity: O(n^2) — Two separate passes of n2 pairs with O(1) hash map operations.
  • Space complexity: O(n^2) — Hash map stores up to n2 distinct pair sums.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force (4 Nested Loops)O(N^4)O(1)Iterate over all i, j, k, l with 4 nested loops and check if sum == 0.Checks all quadruplet combinations independently without reusing partial sums.
2.Sort CD Pairs + Binary SearchO(N^2 log N)O(N^2)Create an array of all CD sums and sort it. For each AB sum, binary search the range of matches.Binary search lookup is slower than O(1) hash map lookups.
3.Hash Map (Meet in the Middle)OptimalO(N^2)O(N^2)Store frequencies of (nums1 + nums2) in Hash Map, lookup -(nums3 + nums4).None. Hash lookups run in O(1) average time.

Common Pitfalls & Crucial Edge Cases

Confusing 4Sum II with 4Sum (LeetCode 18)

4Sum I operates on a single array and requires returning unique value quadruplets without duplicates. 4Sum II operates on 4 distinct arrays and counts distinct index tuples (i, j, k, l)—no deduplication needed.

Grouping 3 vs 1 instead of 2 vs 2

Grouping (nums1, nums2, nums3) into a map produces O(N3) time and O(N3) space, which fails for N = 200.

Storing Indices in Map

Storing a list of index pairs in the hash map uses unnecessary memory. Only the integer frequency count is required.

Modifying Input Arrays

Sorting the 4 arrays is unnecessary and does not improve the O(N2) hash map approach.

Crucial Edge Cases to Validate:

  • Length 1 Arrays (N = 1) — e.g., nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0] -> evaluates 0 + 0 == 0, returning 1.
  • No Valid Quadruplets — If all arrays have only positive numbers (e.g. [1], [1], [1], [1]), target complements will be negative and not found in the map, returning 0.
  • All Zero Arrays — e.g., 4 arrays of size 2 filled with 0s -> sumCount[0] = 4, checked 4 times -> returns 4 * 4 = 16.
  • Large Integer Values — Values up to 228 mean 4 elements sum up to ~1.07 * 109, which fits safely within standard 32-bit signed integer limits.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the equation transformation clearly: Write (nums1[i] + nums2[j]) == -(nums3[k] + nums4[l]) to immediately show your Meet-in-the-Middle intuition.
  2. Clarify index combinations vs value combinations: Explain why this problem is purely frequency accumulation without deduplication.
  3. Analyze time & space complexity: Explicitly justify why N = 200 makes O(N2) space (~40k entries) completely safe for heap memory.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is 2-and-2 splitting (nums1+nums2 and nums3+nums4) optimal compared to 3-and-1 splitting (nums1+nums2+nums3 and nums4)?

2.Why do we NOT need to sort or skip duplicate values in 4Sum II?

3.What is the maximum number of entries stored in the Hash Map when N = 200?

Back to DSA Sheet