Number of Boomerangs

Problem

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

public class Solution {
    public int numberOfBoomerangs(int[][] points) {
        int res = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < points.length; i++) {
            for (int j = 0; j < points.length; j++) {
                if (i == j) continue;
                int distance = getDistance(points[i], points[j]);
                map.put(distance, map.getOrDefault(distance, 0) + 1);
            }
            for (int count: map.values()) res += count * (count - 1);
            map.clear();
        }
        return res;
    }

    //Helper method to get distance between two given points
    private static int getDistance(int[] p1, int[] p2) {
        int deltaX = p1[0] - p2[0];
        int deltaY = p1[1] - p2[1];
        return deltaX * deltaX + deltaY * deltaY;
    }
}

Analysis

The problem gives us a list of points and we need to find out number of boomerangs which is a list of three numbers i, j, k where distance of i and j equalsi and k
Notice that the number of i j k matters in this problem
Therefore, we choose a point i and then loop through all other given points
We store the distance between them into our map
Then we loop the counts of same distance, which is the value of the map
Say we have n same distance of ith point
We put the ith point in the middle of boomerang, we can construct n * (n - 1) different boomerangs Hence we update the res += count * (count + 1)
Do not forget to clear the map after calculating the boomerang of each point

Complexity:

• Time: O(n^2), we have two nested loops
• Space: O(n), we have a hash map to store the distance and their count