454. 4Sum II
Model: qwen3.5:9b
Topics: Hash Table,Binary Search
FAANG asked: 1
Acceptance rate: 54.6%
Problem Breakdown
We are given four integer arrays A, B, C, and D of equal length N. The goal is to find the number of tuples (i, j, k, l) such that the sum of elements at these indices equals zero: A[i] + B[j] + C[k] + D[l] == 0.
Inputs: Four lists (arrays) A, B, C, D. Output: An integer representing the count of valid tuples. Constraints & Edge Cases:
- N ≤ 500: This is a critical constraint. It suggests an or even slightly worse solution might pass in some languages but could be risky; however, standard brute force () will definitely time out. We need something closer to quadratic.
- Integer Range: Values can be negative and large (up to 2^31). Python handles this natively without overflow concerns, unlike fixed-width integer languages like Java or C++. The range is typically to .
- Empty Input: If N=0, the loops won’t execute, returning 0 correctly.
- Duplicates: Arrays may contain duplicate values; we must count every valid index combination, not just unique value combinations.
Intuition
If I were to solve this naively, I would use four nested loops iterating through indices i, j, k, and l. This checks every possible tuple. The time complexity would be . With N=500, that’s roughly 62 billion operations (), which is far too slow for a typical interview limit (usually ~1 second).
To optimize, I need to reduce the number of iterations. Notice the equation: A[i] + B[j] + C[k] + D[l] = 0.
I can rearrange this as (A[i] + B[j]) == -(C[k] + D[l]). This allows me to split the problem into two halves.
Key Insight: I don’t need to iterate through all four arrays simultaneously at once. Instead, I can pre-calculate and store all possible sums from A and B in a hash map (frequency table). Then, for every sum generated by C and D, I check if its negation exists in the stored map. This reduces the complexity significantly because we only need two nested loops per half of the problem.
Approach
- Pre-compute Sums: Iterate through arrays A and B using two nested loops. Calculate
sum_ab = a + b. Store this sum as a key in a hash map (dictionary), where the value is the frequency count of how many times that specific sum occurs. This takes time and space. - Check Complements: Iterate through arrays C and D using two nested loops. Calculate
sum_cd = c + d. The target we are looking for in our hash map is-sum_cd(sincea+b+c+d=0). - Count Matches: If the target exists in the hash map, add its frequency count to a running total of matches found so far. This step also takes time with average dictionary lookups.
- Return Result: Return the accumulated match count after checking all pairs from C and D.
Complexity Analysis
- Time Complexity: . We perform two nested loops over N elements for A/B (generating sums), then another set of nested loops for C/D (checking complements). Dictionary operations are amortized , so the total is proportional to .
- Space Complexity: . In the worst case, every combination of A and B produces a unique sum. The hash map stores up to entries. Given , this is roughly 250k integers, which fits comfortably within memory limits (a few MBs).
Solution
from typing import List
from collections import defaultdict
class Solution:
def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
# Dictionary to store frequency of sums from arrays A and B
sum_map = defaultdict(int)
n = len(A)
# Step 1: Compute all possible sums for A[i] + B[j]
# Time Complexity here is O(N^2)
for a in A:
for b in B:
current_sum = a + b
sum_map[current_sum] += 1
count = 0
# Step 2: Iterate through C and D, checking if -(C[k] + D[l]) exists in map
# Time Complexity here is O(N^2) with O(1) lookup per pair
for c in C:
for d in D:
target = -(c + d)
# If the complement sum exists, add its frequency to count
if target in sum_map:
count += sum_map[target]
return count
Edge Cases Handled
- Empty Arrays: The loops
for a in Awill not execute if N=0.sum_mapremains empty. The second loop also won’t run or finds nothing, returning 0 correctly. - No Solution Found: If no combination sums to zero, the check
if target in sum_mapnever triggers (or returns 0), andcountstays at 0. - Duplicate Values/Indices: The problem asks for tuples of indices
(i, j, k, l). By iterating over elements directly rather than unique values, we implicitly handle duplicates correctly because every occurrence in the list is processed individually by the nested loops. - Negative Numbers: Python’s integer arithmetic handles negative numbers naturally without overflow issues (unlike fixed-width integers), so
-(c + d)works regardless of sign combinations.