Leetcode Problem 454 4Sum II.txt

454. 4Sum II
Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.

To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most 231 - 1.

Example:

Input:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]

Output:
2

Explanation:
The two tuples are:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0


Hint to solve: calculate the sum frequency of any two list and store it in the dictionary
Iterate through other two list and check if the complement of the sum is present in the dictionary. If yes the get the freq and add it to the result.


class Solution:
    def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
        
        sumFreq = {}
        
        for i in range(len(A)):
            for j in range(len(B)):
                total = A[i] + B[j]
                if total in sumFreq:
                    sumFreq[total] += 1
                else:
                    sumFreq[total] = 1
        
        
        result = 0
        for i in range(len(C)):
            for j in range(len(D)):
                complementTotal =(C[i] + D[j]) * -1
                if complementTotal in sumFreq:
                    result += sumFreq[complementTotal]
        
        return result