Is Number of Boomerangs easy or hard?

Number of Boomerangs is rated Medium because the brute-force idea is straightforward but recognizing the frequency counting trick with k * (k - 1) requires insight. Once that observation is made, the implementation becomes simple.

Number of Boomerangs Python/Java solution

Python typically uses a dictionary or collections.defaultdict to count distances, while Java uses HashMap . Both implementations iterate through each point as a center and accumulate k * (k - 1) for matching distances.

How to solve Number of Boomerangs in O(n^2)?

Iterate through each point as the center i. Compute the squared distance from i to every other point and store counts in a hash map. If a distance appears k times, add k * (k - 1) to the answer since order matters between j and k.

What is the best approach for Number of Boomerangs?

The most efficient approach fixes each point as the center and counts distances to all other points using a hash map. For every distance that appears k times, it contributes k * (k - 1) ordered boomerangs. This runs in O(n^2) time and O(n) space and is the standard interview solution.

Is Number of Boomerangs asked at Google/Amazon/Meta?

Problems involving distance grouping, hash map counting, and geometric reasoning appear frequently in interviews at companies like Google, Amazon, and Meta. Number of Boomerangs tests the ability to transform a geometric condition into a counting problem using hashing.

What data structure is used in Number of Boomerangs?

A hash table (HashMap or dictionary) is the primary data structure. It stores the frequency of squared distances from a fixed center point to all other points, enabling constant-time updates and lookups while counting boomerangs.

What is the time complexity of Number of Boomerangs?

The optimal solution runs in O(n^2) time because for each point you compute distances to every other point. The hash map stores frequency counts of distances for that center. Space complexity is O(n) for the distance frequency map.

Description Solution Video 6:53

447. Number of Boomerangs

Medium58.0% acceptance2 companies

You are given n points in the plane that are all distinct, where points[i] = [x_i, y_i]. 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
-10⁴ <= x_i, y_i <= 10⁴
All the points are unique.

Asked at 2 companies

Google Bloomberg

Topics

6:53

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution

447. Number of Boomerangs

Asked at 2 companies

Topics

Similar problems