# Number of Boomerangs
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-boomerangs)
Canonical: https://scaleengineer.com/dsa/problems/number-of-boomerangs
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Array, Hash Table
---
## Problem
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**.

# Approaches
## Brute Force Iteration
This approach involves iterating through all possible combinations of three distinct points (i, j, k) and checking if they form a boomerang. A boomerang is defined by the condition that the distance from point `i` to `j` is equal to the distance from point `i` to `k`.
**Time:** O(n^3), where n is the number of points. We have three nested loops, each iterating up to n times. This makes the approach very slow for larger inputs. · **Space:** O(1). We only use a few variables to store indices and the count, so the extra space required is constant.
**Pros:** Simple to understand and implement.
**Cons:** Highly inefficient due to the cubic time complexity.; Likely to result in a 'Time Limit Exceeded' error for the given constraints (n <= 500).
### Explanation
This approach directly translates the problem definition into code. We check every possible ordered triplet of distinct points `(i, j, k)` to see if it satisfies the boomerang condition: `distance(i, j) == distance(i, k)`. To avoid floating-point precision issues and the performance cost of square roots, we compare the squared distances instead. The squared distance between two points `(x1, y1)` and `(x2, y2)` is `(x1 - x2)^2 + (y1 - y2)^2`. The implementation involves three nested loops to select the three points, followed by a check for the distance equality.

```java
class Solution {
    public int numberOfBoomerangs(int[][] points) {
        int n = points.length;
        if (n < 3) {
            return 0;
        }
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                for (int k = 0; k < n; k++) {
                    if (i == k || j == k) continue;
                    
                    long dist_ij = getSquaredDistance(points[i], points[j]);
                    long dist_ik = getSquaredDistance(points[i], points[k]);
                    
                    if (dist_ij == dist_ik) {
                        count++;
                    }
                }
            }
        }
        return count;
    }

    private long getSquaredDistance(int[] p1, int[] p2) {
        long dx = p1[0] - p2[0];
        long dy = p1[1] - p2[1];
        return dx * dx + dy * dy;
    }
}
```
### Algorithm
1. Initialize a counter `count` to 0.
2. Use three nested loops to iterate through all unique triplets of indices `(i, j, k)`.
3. For each triplet, calculate the squared distance between `points[i]` and `points[j]`, and the squared distance between `points[i]` and `points[k]`.
4. If the two distances are equal, increment the `count`.
5. After checking all triplets, return `count`.

## Optimized Approach with Hash Map
A more efficient approach is to iterate through each point and consider it as the pivot of a potential boomerang. For each pivot point, we can use a hash map to count how many other points are at the same distance from it. This avoids the third loop of the brute-force method.
**Time:** O(n^2), where n is the number of points. The outer loop runs n times (for each pivot). The inner loop also runs n times to calculate distances and populate the hash map. This is a significant improvement over the brute-force approach. · **Space:** O(n). For each pivot point, we use a hash map to store distances. In the worst-case scenario, all other n-1 points are at distinct distances from the pivot, so the map will store n-1 entries.
**Pros:** Much more efficient with a quadratic time complexity.; Passes the time limits for the given constraints.
**Cons:** Uses extra space for the hash map.
### Explanation
We can significantly optimize the process by changing our perspective. Instead of checking every triplet, we can fix one point `i` as the pivot and then find how many pairs `(j, k)` exist that are equidistant from `i`. A hash map is the perfect tool for this.

For each point `i`, we iterate through all other points `j`, calculate the squared distance `d` between `i` and `j`, and store these distances in a hash map. The map will have the distance `d` as the key and the number of points at that distance as the value.

Once the map is built for pivot `i`, we can iterate through it. If `m` points are found at a certain distance, we know we can form `m * (m - 1)` boomerangs. This is a permutation calculation (`P(m, 2)`), as we need to choose an ordered pair of two distinct points from the `m` available points to be `j` and `k`. We sum these counts for all distances and all pivots to get the final answer.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        int totalBoomerangs = 0;
        int n = points.length;
        
        for (int i = 0; i < n; i++) {
            Map<Long, Integer> distanceMap = new HashMap<>();
            
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    continue;
                }
                
                long dist = getSquaredDistance(points[i], points[j]);
                distanceMap.put(dist, distanceMap.getOrDefault(dist, 0) + 1);
            }
            
            for (int count : distanceMap.values()) {
                totalBoomerangs += count * (count - 1);
            }
        }
        
        return totalBoomerangs;
    }

    private long getSquaredDistance(int[] p1, int[] p2) {
        long dx = p1[0] - p2[0];
        long dy = p1[1] - p2[1];
        return dx * dx + dy * dy;
    }
}
```
### Algorithm
1. Initialize `totalBoomerangs = 0`.
2. Iterate through each point `p_i` to serve as the pivot.
3. For each pivot `p_i`, create a `HashMap` to store frequencies of distances to other points.
4. Iterate through all other points `p_j` and populate the map with `(squared_distance, count)`.
5. After populating the map, iterate through its values (`m`).
6. For each count `m`, add `m * (m - 1)` to `totalBoomerangs`.
7. After iterating through all pivots, return `totalBoomerangs`.

# Solutions
### Java

```java
class Solution { public int numberOfBoomerangs ( int [][] points ) { int ans = 0 ; for ( int [] p1 : points ) { Map < Integer , Integer > cnt = new HashMap <>(); for ( int [] p2 : points ) { int d = ( p1 [ 0 ] - p2 [ 0 ]) * ( p1 [ 0 ] - p2 [ 0 ]) + ( p1 [ 1 ] - p2 [ 1 ]) * ( p1 [ 1 ] - p2 [ 1 ]); cnt . merge ( d , 1 , Integer: : sum ); } for ( int x : cnt . values ()) { ans += x * ( x - 1 ); } } return ans ; } }
```

### CPP

```cpp
class Solution { public: int numberOfBoomerangs ( vector < vector < int >>& points ) { int ans = 0 ; for ( auto & p1 : points ) { unordered_map < int , int > cnt ; for ( auto & p2 : points ) { int d = ( p1 [ 0 ] - p2 [ 0 ]) * ( p1 [ 0 ] - p2 [ 0 ]) + ( p1 [ 1 ] - p2 [ 1 ]) * ( p1 [ 1 ] - p2 [ 1 ]); cnt [ d ] ++ ; } for ( auto & [ _ , x ] : cnt ) { ans += x * ( x - 1 ); } } return ans ; } };
```

### Python

```python
class Solution : def numberOfBoomerangs ( self , points : List [ List [ int ]]) -> int : ans = 0 for p1 in points : cnt = Counter () for p2 in points : d = dist ( p1 , p2 ) cnt [ d ] += 1 ans += sum ( x * ( x - 1 ) for x in cnt . values ()) return ans
```