Formatted question description: https://leetcode.ca/all/447.html
447. Number of Boomerangs
Level
Easy
Description
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]]
Solution
For each point
in points
, calculate the distance of any other point
to the current point
, and store the number of point
s for each distance. For each distance, if there are k
points, then there are k * (k - 1)
boomerangs for the current point
. Calculate the sum to obtain the total number of boomerangs.
class Solution {
public int numberOfBoomerangs(int[][] points) {
int count = 0;
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
int numOfPoints = points.length;
for (int i = 0; i < numOfPoints; i++) {
map.clear();
int[] point1 = points[i];
for (int j = 0; j < numOfPoints; j++) {
if (i == j)
continue;
int[] point2 = points[j];
int distanceSquare = distanceSquare(point1, point2);
int distanceCount = map.getOrDefault(distanceSquare, 0);
distanceCount++;
map.put(distanceSquare, distanceCount);
}
Set<Integer> keySet = map.keySet();
for (int key : keySet) {
int distanceCount = map.get(key);
count += distanceCount * (distanceCount - 1);
}
}
return count;
}
public int distanceSquare(int[] point1, int[] point2) {
return (point1[0] - point2[0]) * (point1[0] - point2[0]) + (point1[1] - point2[1]) * (point1[1] - point2[1]);
}
}