Number of Boomerangs

Medium
682.

Number of Boomerangs

Number of Boomerangs is a medium coding problem on arrays, hash table and math, asked in Amazon, Google and Meta interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} points
 * @return {number}
 */
var numberOfBoomerangs = function(points) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

Hints for Number of Boomerangs

  1. Hint 1

    Fix the apex i. Then you need pairs of other points equidistant from it.

  2. Hint 2

    Group the other points by their squared distance to i — square roots are both slower and lossy.

  3. Hint 3

    A group of size m contributes m * (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

  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

Java

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