Teaching Kids Programming – Number of Quadruplets That Sum Target via Hash Table

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).

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.

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:

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.

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) —