Teaching Kids Programming: Videos on Data Structures and Algorithms
Given four lists of integers a, b, c, and d, and an integer target, return the number of unique quadruple i, j, k, l such that a[i] + b[j] + c[k] + d[l] = target.
Constraints
n ≤ 1,000 where n is the length of a
m ≤ 1,000 where m is the length of b
p ≤ 1,000 where p is the length of c
q ≤ 1,000 where q is the length of d
Example 1
Input
a = [4, 3, 2]
b = [7, 3]
c = [5, 1]
d = [3, 9]
target = 19
Output
3
Explanation
These sum to 19
[4, 7, 5, 3]
[2, 3, 5, 9]
[2, 7, 1, 9]We can reduce this problem into a 2-sum problem instead. Can we group the 4 arrays somehow to make use of the 2-sum problem?
Number of Quadruplets That Sum Target via Hash Table
We can bruteforce with O(N^4) with one number from each array. The space complexity is O(1).
1 2 3 4 5 6 7 8 9 10 | class Solution: def solve(self, A, B, C, D, target): ans = 0 for a in A: for b in B: for c in C: for d in D: if a + b + c + d == target: ans += 1 return ans |
class Solution: def solve(self, A, B, C, D, target): ans = 0 for a in A: for b in B: for c in C: for d in D: if a + b + c + d == target: ans += 1 return ans
We can optimize to O(N^3) with a hash map to count and store the numbers in the fourth array.
1 2 3 4 5 6 7 8 9 10 | class Solution: def solve(self, A, B, C, D, target): ans = 0 data = Counter(D) for a in A: for b in B: for c in C: d = target - a - b - c ans += data[d] return ans |
class Solution: def solve(self, A, B, C, D, target): ans = 0 data = Counter(D) for a in A: for b in B: for c in C: d = target - a - b - c ans += data[d] return ans
If the array contains all unique numbers, we can replace the Counter using a simple set.
A better solution would be to split the four arrays into two groups. Then we can count the possible Two-Sum in two sets. Then, iterating over one set, and sum up the multiplication of the counts would give us the number of quadruplets that sum to target:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | class Solution: def numberOfQuadrupletsThatSumToTarget(self, A, B, C, D, target): ab = defaultdict(int) cd = defaultdict(int) for a in A: for b in B: ab[a + b] += 1 for c in C: for d in D: cd[c + d] += 1 cnt = 0 for i in ab: cnt += ab[i] * cd[target - i] return cnt |
class Solution: def numberOfQuadrupletsThatSumToTarget(self, A, B, C, D, target): ab = defaultdict(int) cd = defaultdict(int) for a in A: for b in B: ab[a + b] += 1 for c in C: for d in D: cd[c + d] += 1 cnt = 0 for i in ab: cnt += ab[i] * cd[target - i] return cnt
Alternatively, we can reduce to one set, and bruteforce the two pairs in another two arrays, and add up the count.
1 2 3 4 5 6 7 8 9 10 11 | class Solution: def numberOfQuadrupletsThatSumToTarget(self, A, B, C, D, target): cnt = 0 m = defaultdict(int) for a in A: for b in B: m[a + b] += 1 for c in C: for d in D: cnt += m[target - c - d] return cnt |
class Solution: def numberOfQuadrupletsThatSumToTarget(self, A, B, C, D, target): cnt = 0 m = defaultdict(int) for a in A: for b in B: m[a + b] += 1 for c in C: for d in D: cnt += m[target - c - d] return cnt
Both algorithms take O(N^2) time and O(N^2) space.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Convert UTF-8 Char Array to Raw Byte Array in Java
Next Post: GoLang: FizzBuzz