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.length1 <= n <= 500points[i].length == 2-104 <= xi, yi <= 104- All the points are unique.
Solutions
Solution 1: Enumeration + Counting
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 × (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.
PythonJavaC++GoTypeScript
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(code-box)
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;
}
}(code-box)
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;
}
};(code-box)
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
}(code-box)
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;
}(code-box)
Solution 2
PythonJavaC++GoTypeScript
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(code-box)
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;
}
}(code-box)
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;
}
};(code-box)
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
}(code-box)
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;
}(code-box)
