Number of Boomerangs

Question

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:
[[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]]

Tags

• Hashmap

Thought

Reference: http://bookshadow.com/weblog/2016/11/06/leetcode-number-of-boomerangs/

Use the hashmap to count the number with different distance in the points list. The key of the hashmap is the distance and the value is the count number.

Code

class Solution(object):
    def numberOfBoomerangs(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        ans = 0
        for x1, y1 in points:
            distanceMap = collections.defaultdict(int)
            for x2, y2 in points:
                dist = (x2 - x1)**2 + (y2 - y1)**2
                if dist == 0:
                    continue
                distanceMap[dist] += 1
            for dist in distanceMap.keys():
                ans += distanceMap[dist] * (distanceMap[dist] - 1)
        return ans