Couting triplets (solution II)
I have ended up checking the solution:
Given a triplet form by i,j,k elements in the arr
Looping the array in order guarantee that the elements you found in the triplet are in order i<j<k
The key is to have a two maps where the key are the numbers and the value is the number of triplets that are using that number.
You can build that map at front because it wont cover scenarios like (1,2,1,2,4), where the second "1" can only form triplets with the elements to his right.
For each element:
compute the number of triplets by saying, is the number of times this element
compute the number of different ways to get the second element of triplet.
When an element is process you
For each item we want to check the following:
Is it the second element of the triplet.
If it is add the third
def countTriplets(arr, r):
t2 = defaultdict(int)
t3 = defaultdict(int)
counter =0
for number in arr:
counter += t3[number]
t3[number*r]+=t2[number]
t2[number*r]+=1
return counter
Looping the array in order guarantee that the elements you found in the triplet are in order i<j<k
The key is to have a two maps where the key are the numbers and the value is the number of triplets that are using that number.
You can build that map at front because it wont cover scenarios like (1,2,1,2,4), where the second "1" can only form triplets with the elements to his right.
For each element:
compute the number of triplets by saying, is the number of times this element
compute the number of different ways to get the second element of triplet.
When an element is process you
For each item we want to check the following:
Is it the second element of the triplet.
If it is add the third
Comments
Post a Comment