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.length1 <= n <= 500points[i].length == 2-104 <= xi, yi <= 104Problem Overview: You are given a list of 2D points. A boomerang is an ordered tuple of points (i, j, k) where the distance from i to j equals the distance from i to k. Order matters, so (i, j, k) and (i, k, j) count as different boomerangs. The goal is to count all such tuples across the set of points.
Approach 1: Distance Counting using HashMap (Time: O(n^2), Space: O(n))
Fix one point as the center i. Compute the squared Euclidean distance from i to every other point. Store frequencies of these distances in a HashMap. If a particular distance appears k times, it forms k * (k - 1) ordered pairs because each pair of points at that distance can be arranged in two directions. This approach avoids unnecessary square roots by using squared distance calculations and relies on constant-time hash lookups. The algorithm iterates through all points as centers, making it an efficient hash table based solution combined with simple array iteration.
Approach 2: Pre-computation and Lookup Table (Time: O(n^2), Space: O(n^2))
Instead of recomputing distances for each center point, precompute the pairwise squared distances between every pair of points and store them in a lookup table or matrix. After building this table, iterate over each center i and count how many points share the same distance value relative to i. Use the same combinational formula k * (k - 1) to count ordered pairs. This approach reduces repeated distance calculations but increases memory usage due to the stored matrix. The logic still relies on geometric distance properties from basic math operations.
Recommended for interviews: The hash map distance counting approach is what most interviewers expect. It demonstrates understanding of frequency counting, avoiding redundant work, and translating a geometric condition into a counting problem. Pre-computation can work but uses unnecessary memory. Showing the brute reasoning first (compare distances from a fixed center) and then optimizing with a hash map signals strong problem‑solving skills.
This approach involves treating each point as a base point and calculating the distance to all other points. A hashmap (or dictionary) is used to count occurrences of each distance. For any two points that share the same distance to the base point, we have two boomerangs.
We use a fixed-size array `dist` to store the count of distances from the base point to all other points. For each pair of points with the same distance, two boomerangs can be formed. The array `dist` is reset on every iteration to count new distances for the next base point.
Time complexity is O(n^2) where n is the number of points, and space complexity is O(SIZE) for the distance count array.
This approach involves using a lookup table to pre-compute square distance values. This can reduce some computational overhead during the distance calculation step by avoiding repetitive arithmetic operations.
In this implementation, a static array `dist` is used to store pre-computed square distances for efficient access. The cost of setting up the lookup table is offset by faster access during distance retrieval.
Time complexity remains O(n^2), but the space complexity is larger due to the MAX_DIST array.
We can enumerate each point in points as the boomerang's point i, and then use a hash table cnt to record the number of times the distance from other points to i appears.
If there are x points with equal distance to i, then we can arbitrarily select two of them as the boomerang's j and k. The number of schemes is A_x^2 = x times (x - 1). Therefore, for each value x in the hash table, we calculate and accumulate A_x^2, which gives us the total number of boomerangs that meet the problem's requirements.
The time complexity is O(n^2), and the space complexity is O(n), where n is the length of the array points.
Python
Java
C++
Go
TypeScript
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Distance Counting using HashMap | Time complexity is O(n^2) where n is the number of points, and space complexity is O(SIZE) for the distance count array. |
| Approach 2: Pre-computation and Lookup Table | Time complexity remains O(n^2), but the space complexity is larger due to the MAX_DIST array. |
| Enumeration + Counting | — |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Distance Counting using HashMap | O(n^2) | O(n) | General case and interview settings where memory efficiency and clarity matter |
| Pre-computation with Distance Lookup Table | O(n^2) | O(n^2) | Useful if distances will be reused many times or precomputation is acceptable |
447. Number of Boomerangs | LEETCODE MEDIUM • code Explainer • 2,375 views views
Watch 9 more video solutions →Practice Number of Boomerangs with our built-in code editor and test cases.
Practice on FleetCode