4Sum II

4Sum II

What is this problem about?

The 4Sum II coding problem differs significantly from the original 4Sum. Instead of one array, you are given four separate integer arrays (A, B, C, and D), all of length $n$. Your goal is to find the number of tuples $(i, j, k, l)$ such that $A[i] + B[j] + C[k] + D[l] = 0$. In this version, you don't need to worry about unique quadruplets; you just need to count every possible index combination that works.

Why is this asked in interviews?

Tech giants like Google and Amazon frequently use this problem to test a candidate's knowledge of the Meet-in-the-middle strategy. It’s an exercise in trading space for time. A brute-force $O(N^4)$ solution will fail, so you must demonstrate how to break the problem into two halves to achieve $O(N^2)$ performance.

Algorithmic pattern used

The Hash Table interview pattern is the hero here. You split the four arrays into two pairs. First, you iterate through arrays A and B, calculating every possible sum and storing the frequency of those sums in a Hash Map. Then, you iterate through arrays C and D and check if the negation of their sum ($0 - (C[k] + D[l])$) exists in your map.

Example explanation

Let: $A = [1, 2]$, $B = [-2, -1]$, $C = [-1, 2]$, $D = [0, 2]$

1. Map A+B: $1+(-2)=-1$, $1+(-1)=0$, $2+(-2)=0$, $2+(-1)=1$.

• Map: {-1: 1, 0: 2, 1: 1}

1. Check C+D:

• One sum is $C[0]+D[0] = -1+0 = -1$. Its negation is 1. 1 exists in our map once. Count = 1.
• Another sum is $C[1]+D[0] = 2+0 = 2$. Its negation is -2. Not in map.
• Continue for all 4 combinations of C and D.

Common mistakes candidates make

• Using the wrong 4Sum approach: Candidates often try to use Two Pointers, which is difficult here because the numbers are across four different arrays.
• Memory Management: Creating a Hash Map for three arrays and checking against the fourth ($O(N^3)$) is still too slow. The $2+2$ split is the most efficient.
• Ignoring Counts: Forgetting that if a sum appears 3 times in the first map, it contributes 3 to the total count for every matching pair found in the second half.

Interview preparation tip

Whenever you have multiple independent sets of data and need to find a sum, think about "Meet-in-the-middle." Splitting the work into two equal parts and using a Hash Map to bridge them is a powerful optimization technique.