Problem Description

The "Number of Boomerangs" problem asks you to count the number of boomerang tuples in a set of distinct points on a 2D plane. A boomerang is defined as a tuple of points (i, j, k) such that the distance between point i and point j is equal to the distance between point i and point k. The order of the tuple matters, so (i, j, k) is considered different from (i, k, j).

• You are given a list of points, where each point is represented as [x, y].
• Return the total number of boomerang tuples that can be formed.
• Points are all distinct.
• Do not reuse the same point in a tuple (i.e., i, j, and k are all different).

Thought Process

Let's start by understanding what a boomerang is in this context. For every point i, we want to find all pairs of points (j, k) such that distance(i, j) == distance(i, k) and j != k. Since the order matters, both (i, j, k) and (i, k, j) are counted as separate boomerangs.

The brute-force approach would be to check all possible ordered triplets, but this would be very slow for large inputs. To optimize, we can focus on each point i and count, for each possible distance, how many points are at that distance from i. If there are n points at the same distance from i, then there are n * (n - 1) possible boomerang tuples for that distance (since order matters).

This shift—from checking every triplet to grouping points by distance from a fixed center—makes the solution much more efficient.

Solution Approach

Here’s how we can solve the problem step-by-step:

1. Iterate through each point as the potential center i of a boomerang:
   • For each point i, we want to find out how many other points are the same distance away from i.
2. Use a hash map (dictionary) to count distances:
   • For each other point j, compute the squared Euclidean distance from i to j (we can use squared distance to avoid floating-point errors and it's sufficient for comparison).
   • Store the count of points at each distance in the hash map.
3. Calculate the number of boomerangs for each distance:
   • If there are n points at a particular distance from i, then the number of ordered pairs is n * (n - 1).
   • Add this to the running total.
4. Repeat for all points i and sum the results.

We use a hash map because it allows us to count distances in O(1) time, making the approach efficient.

Example Walkthrough

Let's use the input points = [[0,0], [1,0], [2,0]] as an example.

• For point [0,0]:
  • Distance to [1,0]: 1
  • Distance to [2,0]: 4
  • Counts: 1 point at distance 1, 1 point at distance 4 → No boomerangs (since we need at least 2 points at the same distance).
• For point [1,0]:
  • Distance to [0,0]: 1
  • Distance to [2,0]: 1
  • Counts: 2 points at distance 1 → Number of boomerangs: 2 * 1 = 2 (the tuples are (1,0,2) and (1,2,0)).
• For point [2,0]:
  • Distance to [0,0]: 4
  • Distance to [1,0]: 1
  • Counts: 1 point at distance 4, 1 point at distance 1 → No boomerangs.
• Total boomerangs: 2

This matches the expected output.

Time and Space Complexity

• Brute-force approach:
  • Would involve checking all ordered triplets, which is O(n³) time.
• Optimized approach (hash map):
  • For each point i, we compute distances to all other points: O(n) per point.
  • There are n points, so the total time is O(n²).
  • Space complexity: O(n) for the hash map (since, at most, all other points are at different distances).
• Why: The double loop (for each point, for each other point) gives O(n²), and the hash map is reset for each center point, so space doesn't accumulate.

Summary

The problem can be solved efficiently by focusing on each point as the center and counting how many other points are at the same distance from it. Using a hash map to group points by distance allows us to quickly calculate the number of boomerang tuples in O(n²) time. This approach is far more efficient than brute-force checking of all triplets, and the use of squared distances avoids precision issues. The strategy elegantly leverages counting and combinatorics to produce the correct answer.

Code Implementation

class Solution:
    def numberOfBoomerangs(self, points):
        res = 0
        for i in points:
            dist_map = {}
            for j in points:
                if i == j:
                    continue
                dx = i[0] - j[0]
                dy = i[1] - j[1]
                dist = dx * dx + dy * dy
                dist_map[dist] = dist_map.get(dist, 0) + 1
            for count in dist_map.values():
                res += count * (count - 1)
        return res
      

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        int res = 0;
        for (auto& i : points) {
            unordered_map<int, int> dist_map;
            for (auto& j : points) {
                if (i == j) continue;
                int dx = i[0] - j[0];
                int dy = i[1] - j[1];
                int dist = dx * dx + dy * dy;
                dist_map[dist]++;
            }
            for (auto& kv : dist_map) {
                res += kv.second * (kv.second - 1);
            }
        }
        return res;
    }
};
      

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

var numberOfBoomerangs = function(points) {
    let res = 0;
    for (let i of points) {
        let distMap = new Map();
        for (let j of points) {
            if (i === j) continue;
            let dx = i[0] - j[0];
            let dy = i[1] - j[1];
            let dist = dx * dx + dy * dy;
            distMap.set(dist, (distMap.get(dist) || 0) + 1);
        }
        for (let count of distMap.values()) {
            res += count * (count - 1);
        }
    }
    return res;
};