# Python O(n^2) HashMap solution

• couldn't figure out a faster way so far.

class Solution(object):
def numberOfBoomerangs(self, points):
"""
:type points: List[List[int]]
:rtype: int
"""
if len(points) < 3:
return 0
res = 0
for i in range(len(points)):
pDict = {}
for j in range(len(points)):
if j == i:
continue
dis = pow(points[i][0] - points[j][0], 2) + pow(points[i][1] - points[j][1], 2)
key = str(dis)
if key in pDict:
pDict[key] += 1
else:
pDict[key] = 1
for p in pDict:
if pDict[p] > 1:
res += pDict[p] * (pDict[p] - 1)
return res

• This post is deleted!

• said in Python O(n^2) HashMap solution:

abs

No need to use abs() because you use pow() after it. No matter points[i][0] - points[j][0] is positive or negative the result of pow() will be the same.

• said in Python O(n^2) HashMap solution:

if j == i:
continue

No need to skip the case of j==i since it will be a rare case. The number of points is up to 500. Your code only improve one single point out of 499 points.

• Shorter version:

class Solution(object):
def numberOfBoomerangs(self, points):
"""
:type points: List[List[int]]
:rtype: int
"""
res = 0
for x1, y1 in points:
cnt = {}
for x2,y2 in points:
dist = (x1-x2)**2+(y1-y2)**2
cnt[dist] = cnt.get(dist,0) + 1
for k in cnt:
res += cnt[k]*(cnt[k]-1)
return res

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.