4Sum II
Medium· meet in the middle· hash map
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
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)
