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 points 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]);
}
}