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.