447. Number of Boomerangs

Problem

  • Given n points in the plane that are all pairwise distinct, a "boomerang" is a tuple of points (i, j, k) such that the distance between i and j equals the distance between i and k (the order of the tuple matters).
  • Find the number of boomerangs. You may assume that n will be at most 500 and coordinates of points are all in the range [-10000, 10000] (inclusive).

Example:

Input: 1,0[2,0]]

Output: 2

Explanation: The two boomerangs are 0,0[2,0]] and 2,0[0,0]]

Thought Process

  • understand the definition of distance, dis(i,j) = (i[x] - j[x])**2 + (i[y] - j[y])**2. Here I didn't calculate the sqrt, because it will create float, which might be an issue for dict to search due to accuracy
  • for each point i
  • loop thru the rest points and calculate the distance
  • store distance and the # of points to get that distance in a ht
  • loop thru each distance in the ht and calculate the # of the boomerangs
  • based on the number of points to calculate # of boomerangs is a combinatorics problem: e.g there are m points, then the # of boomerang is C(m,2) = m * (m-1)

White Board

Below is the white board:

Code

class Solution:

    def dis(self, p1, p2):
        return (p1[0] - p2[0])**2 + (p1[1] - p2[1])**2

    def create_ht(self, ele, ht):
        assert type(ht) is dict
        if ele not in ht:
            ht[ele] = 1
        else:
            ht[ele] += 1
        return ht

    def num_boom(self, points):
        res = 0
        for idx in range(len(points)):
            ht = {}
            for jdx in range(len(points)):
                if idx != jdx:
                    temp_dis = self.dis(points[idx], points[jdx])
                    ht = self.create_ht(temp_dis, ht)

            for edge in ht:
                res += ht[edge] * (ht[edge] - 1)

        return res

def test():
    # points = [[0,0],[1,0],[2,0]]
    points = [[0,0],[1,0],[-1,0],[0,1],[0,-1]]
    nb = Solution().num_boom(points)
    print(nb)

test()    

20

Complexity

  • Time complexity is O(n**2)
  • Space complexity is O(n**2), as I created a ht within a loop

Optimization

Not happy with the performance for the current solution, I don't have more optimized solution for this one yet at this moment.