Number of Boomerangs — Medium Problem & Solution

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 <= 500
• points[i].length == 2
• -10000 <= x, y <= 10000
• All points are distinct.

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

1. For each point i, build a map from squared distance to how many other points sit at it.
2. 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.
3. 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 == i puts a zero distance in the tally and invents boomerangs.
• Counting m * (m - 1) / 2 gives 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 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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Count Number of Texts Medium
• Construct String With Repeat Limit Medium
• Minimum Number of Steps to Make Two Strings Anagram II Medium
• Count Vowel Substrings of a String Medium
• Minimum Length of String After Operations Medium
• Sum of Digit Differences of All Pairs Medium