413. Four Lists to Zero
Four warehouses each publish a list of price adjustments, stored in the integer arrays a, b, c and d, which all have the same length n. A purchasing bot picks exactly one adjustment from each warehouse and hopes that the four chosen values cancel out.
Return the number of index tuples (i, j, k, l) with 0 <= i, j, k, l < n such that a[i] + b[j] + c[k] + d[l] == 0. Tuples are counted by their indices, so equal values at different positions count separately. The answer is guaranteed to fit in a 32-bit signed integer. A brute force over all four indices is far too slow for the largest inputs.
Example 1
- Input:
- a = [1,-2]b = [3,0]c = [-1,2]d = [-3,1]
- Output:
- 3
- Explanation:
The index tuples (0,0,0,0), (0,1,1,0) and (1,0,1,0) each sum to zero, and no other tuple does.
Example 2
- Input:
- a = [0,0]b = [0,0]c = [0,0]d = [0,0]
- Output:
- 16
- Explanation:
Every one of the 2^4 = 16 index tuples sums to zero.
Constraints
1 ≤ n ≤ 1000
-106 ≤ a[i], b[i], c[i], d[i] ≤ 106
The answer fits in a 32-bit signed integer.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 4,000 msC++ 1,000 msJava 2,000 msJavaScript 2,000 msTypeScript 2,000 ms
Expected complexity
- Time
- O(n^2)
- Space
- O(n^2)