Number of Boomerangs — Solution in Python, Java & C++
Number of Boomerangs solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Number of Boomerangs is a medium coding problem on arrays, hash table and math, asked in Amazon, Google and Meta interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Math
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A boomerang is an ordered triple of distinct points (i, j, k) such that the distance from i to j equals the distance from i to k. The order of j and k matters, so each unordered pair contributes two boomerangs.
Return the number of boomerangs.
Example 1
Input: points = [[0,0],[1,0],[2,0]]
Output: 2
Explanation: Only the middle point has two others at equal distance, giving the two orderings.
Example 2
Input: points = [[1,1],[2,2],[3,3]]
Output: 2
Example 3
Input: points = [[1,1]]
Output: 0
Constraints
1 <= points.length <= 500points[i].length == 2-10000 <= x, y <= 10000All points are distinct.
Hints for Number of Boomerangs
Hint 1
Fix the apex
i. Then you need pairs of other points equidistant from it.Hint 2
Group the other points by their squared distance to
i— square roots are both slower and lossy.Hint 3
A group of size
mcontributesm * (m - 1)ordered pairs.
How to solve Number of Boomerangs
The apex is the only point that matters for the constraint, so fix it and tally squared distances. A bucket of size m yields m * (m - 1) ordered pairs, which is exactly the number of boomerangs with that apex and that radius.
Approach
- For each point
i, build a map from squared distance to how many other points sit at it. - As you insert each distance, add twice the bucket's current size to the answer — that accounts for both orderings with every earlier point at the same distance.
- Repeat for every apex.
Why it works
Adding 2 * c on insertion telescopes to m * (m - 1) over a bucket that ends at size m, which is the count of ordered pairs drawn from it. Summing over apexes counts each boomerang once, since the apex is determined by the triple.
Complexity
- Time —
O(n²) - Space —
O(n)
Pitfalls
- Using floating-point distances makes equal distances compare unequal; squared integer distances are exact.
- Forgetting to skip
j == iputs a zero distance in the tally and invents boomerangs. - Counting
m * (m - 1) / 2gives unordered pairs, which is half the intended answer.
Reference solution
Python
from typing import List
def numberOfBoomerangs(points: List[List[int]]) -> int:
total = 0
for xi, yi in points:
dist = {}
for xj, yj in points:
d = (xi - xj) ** 2 + (yi - yj) ** 2
if d == 0 and (xi, yi) == (xj, yj):
continue
c = dist.get(d, 0)
total += 2 * c
dist[d] = c + 1
return totalJava
public static int numberOfBoomerangs(int[][] points) {
int total = 0;
for (int i = 0; i < points.length; i++) {
Map<Long, Integer> dist = new HashMap<>();
for (int j = 0; j < points.length; j++) {
if (i == j) continue;
long dx = points[i][0] - points[j][0];
long dy = points[i][1] - points[j][1];
long d = dx * dx + dy * dy;
int c = dist.getOrDefault(d, 0);
total += 2 * c;
dist.put(d, c + 1);
}
}
return total;
}C++
int numberOfBoomerangs(vector<vector<int>>& points) {
int total = 0;
for (size_t i = 0; i < points.size(); i++) {
unordered_map<long long, int> dist;
for (size_t j = 0; j < points.size(); j++) {
if (i == j) continue;
long long dx = points[i][0] - points[j][0];
long long dy = points[i][1] - points[j][1];
long long d = dx * dx + dy * dy;
int c = dist[d];
total += 2 * c;
dist[d] = c + 1;
}
}
return total;
}JavaScript
var numberOfBoomerangs = function(points) {
var total = 0;
for (var i = 0; i < points.length; i++) {
var dist = {};
for (var j = 0; j < points.length; j++) {
if (i === j) continue;
var dx = points[i][0] - points[j][0];
var dy = points[i][1] - points[j][1];
var key = String(dx * dx + dy * dy);
var c = dist[key] === undefined ? 0 : dist[key];
total += 2 * c;
dist[key] = c + 1;
}
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets