Number of Boomerangs
Medium · Math & Geometry · Explanation and code example
Squared-Distance Frequencies
How it works
Fix the middle point of a boomerang and group other points by squared distance from it. A group of size c gives c × (c - 1) ordered pairs. Python adds 2c as each new point enters a group; C++ sums the equivalent final group formula.
Steps
- Choose each point as the center.
- Count squared distances to other points.
- For a new distance occurrence, add twice its prior count, then increment it.
Complexity
- Time: O(n²) expected with hashing.
- Space: O(n).
Things to watch for
- Order matters: swapping the two outer points is a different boomerang.
- Squared distances avoid floating-point comparison.
- The problem guarantees distinct points, so the center’s zero-distance entry contributes nothing.
Python code example
import collections
class Solution:
def numberOfBoomerangs(self, points: list[list[int]]) -> int:
ans = 0
for x1, y1 in points:
count = collections.Counter()
for x2, y2 in points:
ans += 2 * count[(x1 - x2)**2 + (y1 - y2)**2]
count[(x1 - x2)**2 + (y1 - y2)**2] += 1
return ans
C++ code example
class Solution {
public:
int numberOfBoomerangs(vector<vector<int>>& points) {
int ans = 0;
for (const vector<int>& p : points) {
unordered_map<int, int> distCount;
for (const vector<int>& q : points) {
const int dist = getDist(p, q);
++distCount[dist];
}
for (const auto& [_, freq] : distCount)
ans += freq * (freq - 1); // Ordered pairs with this distance
}
return ans;
}
private:
int getDist(const vector<int>& p, const vector<int>& q) {
return pow(p[0] - q[0], 2) + pow(p[1] - q[1], 2);
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.