Problem

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.

Examples

Example 1:

1
2
3
4
5

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:

1
2
3
4

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

Example 3:

1
2
3
4

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

Solution

Method 1 – Hash Map for Distance Counting

Intuition

For each point, we count how many other points are at each possible distance from it. If there are cnt points at the same distance, there are cnt * (cnt - 1) ways to choose two of them in order, forming boomerangs. We use a hash map to count distances efficiently.

Approach

  1. For each point p, initialize a hash map to count distances to all other points.
  2. For each other point q, compute the squared distance from p to q and increment the count in the hash map.
  3. For each distance, add cnt * (cnt - 1) to the answer, where cnt is the number of points at that distance from p.
  4. Return the total number of boomerangs.

Complexity

  • ⏰ Time complexity: O(n^2), where n is the number of points, since we compare every pair of points.
  • 🧺 Space complexity: O(n), for the hash map used for each point.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

from collections import Counter
class Solution:
    def numberOfBoomerangs(self, points: list[list[int]]) -> int:
        ans = 0
        for p in points:
            counter = Counter()
            for q in points:
                dx = p[0] - q[0]
                dy = p[1] - q[1]
                dist = dx * dx + dy * dy
                counter[dist] += 1
            for cnt in counter.values():
                ans += cnt * (cnt - 1)
        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[] p : points) {
            Map<Integer, Integer> counter = new HashMap<>();
            for (int[] q : points) {
                int distance = (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1]);
                counter.put(distance, counter.getOrDefault(distance, 0) + 1);
            }
            for (int val : counter.values()) {
                ans += val * (val - 1);
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

function numberOfBoomerangs(points: number[][]): number {
    let ans = 0;
    for (let p1 of points) {
        let hashMap: Map<number, number> = new Map();
        for (let p2 of points) {
            const distance = (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2;
            hashMap.set(distance, (hashMap.get(distance) || 0) + 1);
        }
        for (let [, v] of [...hashMap]) {
            ans += v * (v - 1);
        }
    }
    return ans;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func numberOfBoomerangs(points [][]int) int {
	ans := 0
	for _, p := range points {
		cnt := make(map[int]int)
		for _, q := range points {
			cnt[(p[0]-q[0])*(p[0]-q[0])+(p[1]-q[1])*(p[1]-q[1])]++
		}
		for _, v := range cnt {
			ans += v * (v - 1)
		}
	}
	return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        int ans = 0;
        for (const auto& p : points) {
            unordered_map<int, int> cnt;
            for (const auto& q : points) {
                ++cnt[(p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1])];
            }
            for (const auto& [_, v] : cnt) {
                ans += v * (v - 1);
            }
        }
        return ans;
    }
};

…