Leetcode 447. Number of Boomerangs

Problem Explanation

Given n points in a 2-D plane, a boomerang is defined as a tuple of points (i, j, k) such that the distance between point i and j is equal to the distance between point i and k.

We are to find the total number of boomerangs we can create from the given points.

For Example, consider the points [[0,0],[1,0],[2,0]], the distance between the points [[1,0],[0,0]] and [[1,0],[2,0]] is the same hence we can have boomerangs [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]].

Solution Explanation

In the proposed solution, we use a hashmap to keep track of the distance between points and their frequency. For each point, we calculate the distances with all other points and store those distances in the hashmap. Once we have calculated all distances for a given point, we calculate the number of boomerangs that can be created with this point using the formula n * (n-1) where n is the frequency of a distance and add it to our answer. We repeat this process for all points.

Python Solution

1
2python
3class Solution:
4    def numberOfBoomerangs(self, points):
5        # Track the total number of boomerangs
6        ans = 0
7        for p in points:
8            distCount = collections.defaultdict(int)
9            for q in points:
10                # Calculate the squared distance
11                distCount[(p[0]-q[0])**2+(p[1]-q[1])**2] += 1
12                
13            for freq in distCount.values(): 
14                # Multiply by (n-1) to account for permutations
15                ans += freq * (freq - 1)
16                
17        return ans

Java Solution

1
2java
3class Solution {
4    public int numberOfBoomerangs(int[][] points) {
5        int res = 0;
6
7        Map<Integer, Integer> map = new HashMap<>();
8        for(int i=0; i<points.length; i++) {
9            for(int j=0; j<points.length; j++) {
10                if(i == j)
11                    continue;
12
13                int d = getDistance(points[i], points[j]);                
14                map.put(d, map.getOrDefault(d, 0) + 1);
15            }
16
17            for(int val : map.values()) {
18                res += val * (val-1);
19            }            
20            map.clear();
21        }
22
23        return res;
24    }
25
26    private int getDistance(int[] a, int[] b) {
27        int dx = a[0] - b[0];
28        int dy = a[1] - b[1];
29
30        return dx*dx + dy*dy;
31    }
32}

JavaScript Solution

1
2javascript
3var numberOfBoomerangs = function(points) {
4    var count = 0;
5    for(var i=0;i<points.length;i++) {
6        var map = new Map();
7        for(var j=0;j<points.length;j++) {
8            if(i != j) {
9                var d = getDistance(points[i], points[j]);
10                map.set(d, map.has(d) ? map.get(d)+1 : 1);
11            }
12        }
13        map.forEach(function(value, key) {
14            count += value*(value-1);
15        });
16    }
17    return count;
18};
19
20var getDistance = function(p1, p2) {
21    var x = p1[0] - p2[0];
22    var y = p1[1] - p2[1];
23    return x*x + y*y;
24};

C++ Solution

1
2c++
3class Solution {
4public:
5    int numberOfBoomerangs(vector<vector<int>>& points) {
6        int res = 0;
7        int n = points.size();
8        unordered_map<long, int> distances;
9
10        for(int i=0; i<n; ++i){
11            for(int j=0; j<n; ++j){
12                if(j==i) continue;
13                int dx = points[i][0] - points[j][0];
14                int dy = points[i][1] - points[j][1];
15                int d = dx*dx + dy*dy;
16                res+=distances[d]++;
17            }
18            distances.clear();
19        }
20
21        return res*2;
22    }
23};

C# Solution

1
2csharp
3public class Solution {
4    public int NumberOfBoomerangs(int[][] points) {
5        int res = 0;
6        Dictionary<int,int> record = new Dictionary<int,int>();
7        for (int i = 0; i < points.Length; i++){
8            for (int j = 0; j < points.Length; j++){
9                if (j != i){
10                    int dis = getDistance(points[i], points[j]);
11                    if (record.ContainsKey(dis)){
12                        res += 2* record[dis];
13                    }
14                    if (!record.ContainsKey(dis)){
15                        record[dis] = 1;
16                    }
17                    else{
18                        record[dis]++;
19                    } 
20                }
21            }
22            record.Clear();
23        }
24        return res;
25    }
26
27    private int getDistance(int[] pa, int[] pb){
28        return (pa[0] - pb[0])*(pa[0] - pb[0]) + (pa[1] - pb[1])*(pa[1] - pb[1]);
29    }
30}

These solutions all employ a similar algorithm. They iterate over the arrays of points and for each point calculate the distances to all other points. A property of boomerangs is utilized here: they consist of permutations of three points, where one is the 'anchor' and the other two can be swapped. This property allows us to calculate only the distances from one point to all others and count how many of those distances are equal. This count is then multiplied by (count - 1) to account for the permutations (the two possible arrangements) of each boomerang.

Please note that we are using the square of the Euclidean distance here, since the absolute distance is not necessary for this problem. The computational overhead of square rooting can thus be avoided. Also, in the Java, JavaScript and C# solutions, square of distance is stored in the hashmap so as to avoid floating point precision errors that may arise if we used the absolute distance.

The time complexity of these solutions is O(n^2), where n is the number of points. The space complexity is O(n), as in the worst case scenario we may have to store the distance from one point to all other points in the hashmap. These solutions are efficient and solve the problem in a straightforward manner.

One possible point of optimization could be to employ the continue statement when the indices of two points being compared are the same, to avoid unnecessary computation (comparing a point with itself). This is done in the C++ and Java solutions. For the Python and JavaScript solutions, an if condition could be added at the start of the inner loop to skip the rest of the loop body when p is the same as q (Python) or i is the same as j (JavaScript). The time complexity remains the same, but it reduces the number of unnecessary operations slightly.

Also, note that the collections module has been used in the Python solution to initialize and use the dictionary in a convenient way. In the other solutions, dictionary or map initialization and usage is done in a more manual way.