4Sum II
Medium· meet in the middle· hash map
Problem
Given four integer arrays of equal length n, count the tuples (i, j, k, l) such that A[i] + B[j] + C[k] + D[l] equals zero. Checking all n^4 tuples is too slow.
Examples
Input: A = [1,2], B = [-2,-1], C = [-1,2], D = [0,2]
Output: 2
For example 1 + (-2) + (-1) + 2 = 0 and 2 + (-1) + (-1) + 0 = 0.
Input: A = [0], B = [0], C = [0], D = [0]
Output: 1
Constraints
- • 1 <= n <= 200
- • -2^28 <= values <= 2^28
Hints & approach
Hint 1
Split the four arrays into two pairs.
Hint 2
Count how often each sum A[i] + B[j] appears.
Hint 3
For each C[k] + D[l], look up how many first-half sums cancel it.
Approachtry the hints first
Build a hash map counting every sum a + b over A and B, which takes n^2 time. Then loop over every pair (c, d) from C and D and add count[-(c + d)] to the answer. This meet-in-the-middle split turns an O(n^4) search into two O(n^2) passes, with the map holding up to n^2 entries.
Time O(n^2) · Space O(n^2)