{x}
blog image

Number of Boomerangs

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.length
  • 1 <= n <= 500
  • points[i].length == 2
  • -104 <= xi, yi <= 104
  • All the points are unique.

Solution Explanation for LeetCode 447: Number of Boomerangs

This problem asks to find the number of boomerangs in a set of points. A boomerang is a triplet of points (i, j, k) where the distance between i and j is equal to the distance between i and k.

Approach

The most efficient approach uses a hash map to count distances. The algorithm iterates through each point as the central point 'i'. For each central point, it calculates the squared Euclidean distance to all other points. These distances are stored in a hash map, where the key is the squared distance and the value is the count of points at that distance.

Once the distances are counted, the number of boomerangs involving the central point is calculated. If there are 'x' points at a certain distance from the central point, then the number of boomerangs formed is x * (x - 1) (this is because we need to choose 2 points from x points which is given by nC2). We sum this value for all distances to get the total number of boomerangs for that central point. Finally, we sum the boomerang counts for all central points to get the final answer.

Time and Space Complexity Analysis

  • Time Complexity: O(n^2). The nested loops iterate through all pairs of points, resulting in a time complexity of O(n^2), where n is the number of points. Hash map operations (insertion and retrieval) take constant time on average.

  • Space Complexity: O(n). In the worst case, the hash map might store distances for all points, resulting in O(n) space complexity.

Code Implementation in Multiple Languages

Python

from collections import Counter
 
def numberOfBoomerangs(points):
    ans = 0
    for i in range(len(points)):
        distances = Counter()
        for j in range(len(points)):
            dist_sq = (points[i][0] - points[j][0])**2 + (points[i][1] - points[j][1])**2
            distances[dist_sq] += 1
        for count in distances.values():
            ans += count * (count - 1)
    return ans

Java

import java.util.HashMap;
import java.util.Map;
 
class Solution {
    public int numberOfBoomerangs(int[][] points) {
        int ans = 0;
        for (int i = 0; i < points.length; i++) {
            Map<Integer, Integer> distances = new HashMap<>();
            for (int j = 0; j < points.length; j++) {
                int distSq = (points[i][0] - points[j][0]) * (points[i][0] - points[j][0]) + 
                             (points[i][1] - points[j][1]) * (points[i][1] - points[j][1]);
                distances.put(distSq, distances.getOrDefault(distSq, 0) + 1);
            }
            for (int count : distances.values()) {
                ans += count * (count - 1);
            }
        }
        return ans;
    }
}

C++

#include <vector>
#include <unordered_map>
 
using namespace std;
 
class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        int ans = 0;
        for (int i = 0; i < points.size(); i++) {
            unordered_map<long long, int> distances; // Use long long to avoid overflow
            for (int j = 0; j < points.size(); j++) {
                long long distSq = (long long)(points[i][0] - points[j][0]) * (points[i][0] - points[j][0]) + 
                                   (long long)(points[i][1] - points[j][1]) * (points[i][1] - points[j][1]);
                distances[distSq]++;
            }
            for (auto const& [key, val] : distances) {
                ans += val * (val - 1);
            }
        }
        return ans;
    }
};

JavaScript

/**
 * @param {number[][]} points
 * @return {number}
 */
var numberOfBoomerangs = function(points) {
    let ans = 0;
    for (let i = 0; i < points.length; i++) {
        let distances = {};
        for (let j = 0; j < points.length; j++) {
            let distSq = (points[i][0] - points[j][0])**2 + (points[i][1] - points[j][1])**2;
            distances[distSq] = (distances[distSq] || 0) + 1;
        }
        for (let count of Object.values(distances)) {
            ans += count * (count - 1);
        }
    }
    return ans;
};

These code examples all follow the same algorithmic approach, differing only in syntax and data structures specific to each language. Remember to handle potential integer overflow when calculating the squared distance, as shown in the C++ example using long long.