Count Triplets

  • + 1 comment

    I solved this using two hashmaps/dictionaries. The idea is to iterate using the middle element (let's call it i) of the triplet, and maintaining two hashmaps/dictionaries, one which holds all the elements before i, and the other holds all the elements after i. At the beginning of each iteration, remove i from the after hashmap, and at the end of each iteration, add i to the before hashmap.

    Here is the solution implemented in python:

    def countTriplets(arr, r):
        after = {}
        before = {}
        for a in arr:
            after[a] = after[a] + 1 if a in after else 1
            before[a] = 0
            
        pairs = 0
    
        for num in arr:
            after[num] -= 1
            af = num * r
            bf = num / r
    
            if af in after and bf in before:
                pairs += (after[af] * before[bf])
            
                
            before[num] += 1
    
        return pairs