Number of Boomerangs

• LeetCode: 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).

• Examples:

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]]

• Analysis:

A tuple (i, j, k) for a boomerang is that dist(i, j) is equal to dist (i, k).

For every i, we count the number of every dist(i, m), m is nodes except for i.

So, we can get the number of boomeranges.

For the number k of a distance d, the number of boomerangs is k * (k - 1).

• Code - Java

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        int len = points.length;
        int result = 0;
        for (int i = 0; i < len; i++) {
            int x = points[i][0];
            int y = points[i][1];
            Map<Integer, Integer> counts = new HashMap<Integer, Integer>();
            for (int j = 0; j < len; j++) {
                int x1 = points[j][0];
                int y1 = points[j][1];
                int difx = x1 - x;
                int dify = y1 - y;
                int val = difx * difx + dify * dify;
                int count = counts.getOrDefault(val, 0) + 1;
                counts.put(val, count);
            }
            for (Integer key : counts.keySet()) {
                int val = counts.get(key);
                result += val * (val - 1);
            }
        }
        return result;
    }
}

• Code - C++:

class Solution {
public:
    int numberOfBoomerangs(vector<pair<int, int>>& points) {
        int len = points.size();
        int result = 0;
        for (int i = 0; i < len; i++) {
            int x = points[i].first;
            int y = points[i].second;
            map<int, int> counts;
            for (int j = 0; j < len; j++) {
                int x1 = points[j].first;
                int y1 = points[j].second;
                int difx = x1 - x;
                int dify = y1 - y;
                int val = difx * difx + dify * dify;
                if (counts.find(val) != counts.end()) {
                    counts[val] = counts[val] + 1;
                } else {
                    counts.insert(pair<int, int>(val, 1));
                }
            }
            for (map<int, int>::iterator it = counts.begin(); it != counts.end(); ++it) {
                int val = it->second;
                result += val * (val - 1);
            }
        }
        return result;
    }
};

• Code - Python:

class Solution(object):
    def numberOfBoomerangs(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        pointsLen = len(points)
        result = 0
        for i in range(pointsLen):
            x = points[i][0]
            y = points[i][1]
            counts = {}
            for j in range(pointsLen):
                x1 = points[j][0]
                y1 = points[j][1]
                difx = x1 - x
                dify = y1 - y
                val = difx ** 2 + dify ** 2
                if val in counts:
                    counts[val] = counts[val] + 1
                else:
                    counts[val] = 1
            for key in counts:
                val = counts[key]
                result += val * (val - 1)
        return result

• Time Complexity: O(N^2), N is the length of points

• Space Complexity: O(M), M is the number of distance distance