basically what I do is for each point i, i calculate the distance to all the other points, and I store it in a hashmap. So for each point i, the key in the hashmap is a particular distance, and the value is the number of points that are that distance away from i.
Now, say we know that X points are Y away from i, given this, we can calculate the number of boomerangs involving i and the X points by simply using permutations formula, which is:
n!/(n-r)!r!, in our case r = 2, so it simplifies to n*(n-1).
class Solution(object): def numberOfBoomerangs(self, points): """ :type points: List[List[int]] :rtype: int """ boomerang_cnt = 0 for i in xrange(len(points)): dist_from_i = defaultdict(int) for j in xrange(len(points)): if i != j: dist_j_i = (points[i] - points[j])**2 + (points[i] - points[j])**2 dist_from_i[dist_j_i] += 1 for dist, num_points in dist_from_i.iteritems(): boomerang_cnt += num_points*(num_points - 1) return boomerang_cnt