class Solution:
def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
"""
Brute Force
tc O(NM) sc O(max(N,M))
variation of two sum?
cache nums1 and nums2's item^2 value seperately and loop x comparing with target y^2 and record expected z = y^2/x
"""
A = combinations(nums1,2)
B = combinations(nums2,2)
A1 = [reduce((lambda x,y:x*y),list(AA)) for AA in A]
B1 = [reduce((lambda x,y:x*y),list(BB)) for BB in B]
cntA = Counter(A1)
cntB = Counter(B1)
res = 0
for a in nums1:
if a*a in cntB:
res += cntB[a*a]
for b in nums2:
if b*b in cntA:
res += cntA[b*b]
return res
#############################restructrue code ######################################
class Solution:
def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
# get cnt for current array A given a value from array B
def twoPro(xx,A):
d = {}
cnt = 0
for a in A:
if xx % a == 0:
cnt += d.get(xx/a,0)
d[a] = d.get(a,0) +1
return cnt
res = 0
for x in nums1:
res += twoPro(x*x,nums2)
for y in nums2:
res += twoPro(y*y,nums1)
return res
Optimization: Memoization by hashmap or sorting (hence duplicates can next to each other ) under sacrafice of dupliacates
class Solution:
def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
"""
sort one of the array to make duplicates next to each other, only cnt unique number's combinations
"""
def twoPro(xx,A):
d = {}
cnt = 0
for a in A:
if xx % a == 0:
cnt += d.get(xx/a,0)
d[a] = d.get(a,0) +1
return cnt
def cntArray(A,B):
res,lastRes,last_num = 0,0,0
A.sort()
for i in range(len(A)):
if A[i] == last_num: # duplicate
res += lastRes
else:
lastRes = twoPro(A[i]*A[i],B)
res += lastRes
last_num = A[i]
return res
return cntArray(nums1,nums2)+cntArray(nums2,nums1)