Skip to content

447. Number of Boomerangs

Description

You are given n points in the plane that are all distinct, where points[i] = [xi, yi]. 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).

Return the number of boomerangs.

 

Example 1:

Input: points = [[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]].

Example 2:

Input: points = [[1,1],[2,2],[3,3]]
Output: 2

Example 3:

Input: points = [[1,1]]
Output: 0

 

Constraints:

  • n == points.length
  • 1 <= n <= 500
  • points[i].length == 2
  • -104 <= xi, yi <= 104
  • All the points are unique.

Solutions

Solution 1: Enumeration + Counting

Thinking

A boomerang is an ordered triple; enumerating three points is \(O(n^3)\). After fixing \(i\), points at the same distance from \(i\) may be paired as \((j,k)\) in any order.

For each center \(p_1\), count distances to the others. Seeing a distance already stored \(x\) times creates \(x\) ordered pairs; doubling accounts for both directions.

Accumulate while inserting so the hash map is not scanned again.

We can enumerate each point in points as the boomerang's point \(i\), and then use a hash table \(cnt\) to record the number of times the distance from other points to \(i\) appears.

If there are \(x\) points with equal distance to \(i\), then we can arbitrarily select two of them as the boomerang's \(j\) and \(k\). The number of schemes is \(A_x^2 = x \times (x - 1)\). Therefore, for each value \(x\) in the hash table, we calculate and accumulate \(A_x^2\), which gives us the total number of boomerangs that meet the problem's requirements.

The time complexity is \(O(n^2)\), and the space complexity is \(O(n)\), where \(n\) is the length of the array points.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        ans = 0
        for p1 in points:
            cnt = Counter()
            for p2 in points:
                d = dist(p1, p2)
                ans += cnt[d]
                cnt[d] += 1
        return ans << 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public int numberOfBoomerangs(int[][] points) {
        int ans = 0;
        for (int[] p1 : points) {
            Map<Integer, Integer> cnt = new HashMap<>();
            for (int[] p2 : points) {
                int d = (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]);
                ans += cnt.getOrDefault(d, 0);
                cnt.merge(d, 1, Integer::sum);
            }
        }
        return ans << 1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        int ans = 0;
        for (auto& p1 : points) {
            unordered_map<int, int> cnt;
            for (auto& p2 : points) {
                int d = (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]);
                ans += cnt[d];
                cnt[d]++;
            }
        }
        return ans << 1;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func numberOfBoomerangs(points [][]int) (ans int) {
    for _, p1 := range points {
        cnt := map[int]int{}
        for _, p2 := range points {
            d := (p1[0]-p2[0])*(p1[0]-p2[0]) + (p1[1]-p2[1])*(p1[1]-p2[1])
            ans += cnt[d]
            cnt[d]++
        }
    }
    ans <<= 1
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function numberOfBoomerangs(points: number[][]): number {
    let ans = 0;
    for (const [x1, y1] of points) {
        const cnt: Map<number, number> = new Map();
        for (const [x2, y2] of points) {
            const d = (x1 - x2) ** 2 + (y1 - y2) ** 2;
            ans += cnt.get(d) || 0;
            cnt.set(d, (cnt.get(d) || 0) + 1);
        }
    }
    return ans << 1;
}

Solution 2

Thinking

Solution 1 adds on the fly. Completing the counts first and summing \(x(x-1)\) for each frequency is \(A_x^2\) written out. Same asymptotics, slightly more direct.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        ans = 0
        for p1 in points:
            cnt = Counter()
            for p2 in points:
                d = dist(p1, p2)
                cnt[d] += 1
            ans += sum(x * (x - 1) for x in cnt.values())
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public int numberOfBoomerangs(int[][] points) {
        int ans = 0;
        for (int[] p1 : points) {
            Map<Integer, Integer> cnt = new HashMap<>();
            for (int[] p2 : points) {
                int d = (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]);
                cnt.merge(d, 1, Integer::sum);
            }
            for (int x : cnt.values()) {
                ans += x * (x - 1);
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        int ans = 0;
        for (auto& p1 : points) {
            unordered_map<int, int> cnt;
            for (auto& p2 : points) {
                int d = (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]);
                cnt[d]++;
            }
            for (auto& [_, x] : cnt) {
                ans += x * (x - 1);
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func numberOfBoomerangs(points [][]int) (ans int) {
    for _, p1 := range points {
        cnt := map[int]int{}
        for _, p2 := range points {
            d := (p1[0]-p2[0])*(p1[0]-p2[0]) + (p1[1]-p2[1])*(p1[1]-p2[1])
            cnt[d]++
        }
        for _, x := range cnt {
            ans += x * (x - 1)
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function numberOfBoomerangs(points: number[][]): number {
    let ans = 0;
    for (const [x1, y1] of points) {
        const cnt: Map<number, number> = new Map();
        for (const [x2, y2] of points) {
            const d = (x1 - x2) ** 2 + (y1 - y2) ** 2;
            cnt.set(d, (cnt.get(d) || 0) + 1);
        }
        for (const [_, x] of cnt) {
            ans += x * (x - 1);
        }
    }
    return ans;
}

Comments