BinarySearch 0454 Number of Quadruplets That Sum Target

Problem statement

https://binarysearch.com/problems/Number-of-Quadruplets-That-Sum-Target/

Solution

Equal to Leetcode 0454. 4Sum II.

Complexity

It is O(n^2) for time and space, where n is the biggest length of A, B, C, D.

Code

class Solution:
    def solve(self, A, B, C, D, target):
        Cnt1, Cnt2, ans = Counter(), Counter(), 0
        for a, b in product(A, B):
            Cnt1[a + b] += 1
            
        for c, d in product(C, D):
            Cnt2[c + d] += 1
            
        for val in Cnt1:
            if target - val in Cnt2:
                ans += Cnt1[val]*Cnt2[target - val]
                
        return ans