4Sum II - Video Solutions

Problem Overview: You are given four integer arrays A, B, C, and D. The goal is to count how many tuples (i, j, k, l) satisfy A[i] + B[j] + C[k] + D[l] = 0. A naive approach checks every possible combination, but the real challenge is reducing the exponential search using a smarter lookup strategy.

Approach 1: Brute Force with Four Nested Loops (O(n⁴) time, O(1) space)

The most direct method iterates through every element of all four arrays using four nested loops. For each combination (i, j, k, l), compute the sum and increment the result when it equals zero. This approach demonstrates the full search space and confirms correctness, but it quickly becomes impractical as n grows. With arrays of size 200, the algorithm may check billions of combinations. This version mainly serves as a conceptual baseline before optimizing with better data structures.

Approach 2: Hash Map Pair Sums (O(n²) time, O(n²) space)

The optimal solution reduces the four-sum problem into two independent two-sum problems. First iterate through arrays A and B and compute every possible pair sum a + b. Store these sums in a hash map where the key is the sum and the value is the number of times that sum appears. This preprocessing step takes O(n2) time.

Next iterate through arrays C and D. For each pair compute c + d, then check if -(c + d) exists in the hash map. A constant-time hash lookup immediately tells you how many matching pairs from A and B can complete the equation. Add that frequency to the answer. This effectively counts all tuples whose sums cancel out to zero.

The key insight: instead of evaluating four numbers at once, precompute half of the equation and reuse it with fast lookups. The hash table stores pair frequencies, while the arrays are scanned with simple nested loops. This reduces the search space from n⁴ combinations to roughly 2 * n² operations. The idea is common in multi-sum problems and builds directly on patterns from array pair-sum techniques.

Recommended for interviews: Interviewers expect the hash map pair-sum solution. Starting with the brute force approach shows you understand the problem space, but optimizing to O(n²) using a frequency map demonstrates algorithmic insight and familiarity with hash-based counting patterns. This approach balances performance and clarity, and it is the standard solution used in most production implementations.