## 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.

Example:

```
Input:
[[0,0],[1,0],[2,0]]
Output:
2
Explanation:
The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[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.