Watch 10 video solutions for Number of Boomerangs, a medium level problem involving Array, Hash Table, Math. This walkthrough by code Explainer has 2,375 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |