Problem Description
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.
Key Insights
- A boomerang is defined by an origin point and two other points that are equidistant from it.
- The distance between points can be calculated using the squared Euclidean distance to avoid floating-point inaccuracies.
- We can use a hash map to count occurrences of distances from each point to others, which allows us to efficiently determine the number of valid boomerangs.
Space and Time Complexity
Time Complexity: O(n^2) - We need to compare each point with every other point. Space Complexity: O(n) - We use a hash map to store the distances.
Solution
To solve the problem, we will iterate through each point, treating it as the origin. For each origin, we will calculate the squared distance to every other point and store these distances in a hash map. The number of boomerangs can then be computed using the counts in the hash map: for each distance with a count greater than one, the number of boomerangs is given by count * (count - 1), as we can choose two different points from those counted to form the boomerangs.