Four Lists to Zero
MediumArrays & Hashing
Problem
A lab measures four independent error sources, each with a list of possible offsets: a, b, c and d, all of the same length n. A configuration picks one offset from each list, and it is calibrated if the four offsets cancel out exactly.
Return the number of index tuples (i, j, k, l) such that a[i] + b[j] + c[k] + d[l] == 0.
Example 1
- Input:
- a = [1, -1], b = [0, 2], c = [-1, 1], d = [0, -2]
- Output:
- 6
a+b sums are {1, 3, -1, 1}; c+d sums are {-1, -3, 1, -1}. Matching each c+d sum s with a+b sums equal to -s gives 2 + 1 + 1 + 2 = 6.
Example 2
- Input:
- a = [0], b = [0], c = [0], d = [0]
- Output:
- 1
Constraints
- 1 ≤ n ≤ 200
- -2^28 ≤ values ≤ 2^28
Hint
Show the first hint
Four nested loops are n^4. Can you split the four lists into two halves?
Walkthrough
How to approach it
01Clarify before coding
- Are tuples counted by index, so equal values at different indices count separately? Yes.
- Do all lists have the same length? Yes, n each.
- Can the answer be large? Up to n^4 = 1.6·10^9, which fits in 64-bit / JS numbers.
02Brute force
Four nested loops over i, j, k, l, testing the sum.
Cost: O(n^4) time: 1.6·10^9 iterations for n = 200, far too slow. Three loops plus a hash map of d is O(n³) = 8·10^6, better but not the best.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.