Number of Boomerangs

A boomerang is a tuple of points where the distance between the first and second points is the same as the distance between the first and third points.

Here’s a Python code that returns the number of boomerangs for a given set of points:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        def distance(p1, p2):
            return (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2

        result = 0

        for p in points:
            distance_count = {}
            for q in points:
                if p != q:
                    d = distance(p, q)
                    distance_count[d] = distance_count.get(d, 0) + 1

            for count in distance_count.values():
                result += count * (count - 1)

        return result

Explanation:

  1. Define a Distance Function: We create a function distance to calculate the squared distance between two points. We use squared distance to avoid using the square root, as the relative distances will remain the same.
  2. Iterate Through Points: We iterate through each point and compute the distances between that point and all other points in the set.
  3. Count Distances: We use a dictionary distance_count to count how many times each squared distance occurs.
  4. Calculate Boomerangs: For each unique distance, if there are n occurrences, there are n * (n - 1) possible ways to choose the other two points for the boomerang. We sum this value for all distances.
  5. Return the Result: Finally, we return the total count of boomerangs.

This solution has a time complexity of (O(n^2)), where (n) is the number of points.