Code Logo

Number of Boomerangs

Published at24 Jul 2026
Created by
Medium 6 views
Like0

You are given n points in the plane represented as integer coordinate pairs. 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 matters: (i, j, k) is different from (i, k, j). Count the number of boomerangs for all possible i, j, k combinations.

A brute force triple loop would check all O(n³) combinations, which is far too slow for n up to 500. The hash map approach reduces this to O(n²) by fixing each point i as the anchor and grouping all other points by their squared distance from i. For each distance group with m points, the number of ordered pairs (j, k) where both are at the same distance from i is m * (m - 1), because you pick j (m choices) and then k (m - 1 remaining choices).

Squared distances are used instead of actual distances to avoid floating point precision issues. The squared distance between (x1, y1) and (x2, y2) is (dx)² + (dy)², which is always an integer for integer coordinates.

Edge cases include fewer than 3 points (return 0), all points coincident (each pair contributes), and points forming a regular polygon (many symmetric boomerangs).

The number of points n is typically between 1 and 500. The O(n²) hash map approach comfortably handles this limit. The total result can be as large as n * (n - 1) in the worst case, which fits within a 32-bit integer for the given constraints.

Example Input & Output

Example 1
Input
[[1,1],[2,2],[3,3]]
Output
2
Explanation

Distance 2 from (2,2) to both ends.

Example 2
Input
[[0,0],[1,0],[0,1]]
Output
2
Explanation

Boomerangs centered at (0,0).

Example 3
Input
[[0,0],[1,0],[2,0]]
Output
2
Explanation

Boomerangs: (0,1,2) and (0,2,1).

Example 4
Input
[[0,0]]
Output
0
Explanation

Single point, no boomerangs.

Example 5
Input
[[0,0],[1,0],[-1,0],[0,1],[0,-1]]
Output
20
Explanation

Boomerangs centered at origin.

Algorithm Flow

Recommendation Algorithm Flow for Number of Boomerangs

Solution Approach

Count the number of boomerangs (tuples (i, j, k) where distance(i,j) = distance(i,k)). For each point i, compute distances to all other points. Use a hash map counting how many points share each distance. For each distance with n points, there are n * (n-1) boomerang combinations with i as the vertex.

function numberOfBoomerangs(points) {
  var count = 0;
  for (var i = 0; i < points.length; i++) {
    var dists = {};
    for (var j = 0; j < points.length; j++) {
      if (i === j) continue;
      var dx = points[i][0] - points[j][0], dy = points[i][1] - points[j][1];
      var d = dx * dx + dy * dy;
      dists[d] = (dists[d] || 0) + 1;
    }
    for (var d in dists) {
      count += dists[d] * (dists[d] - 1);
    }
  }
  return count;
}

For each vertex i, group other points by squared distance. With n points at the same distance, there are n choices for j and (n-1) remaining choices for k after picking j.

Time complexity is O(n^2), space complexity is O(n).

Best Answers

java
import java.util.*;
class Solution {
    public int solution(int[][] points) {
        int count = 0;
        for (int i = 0; i < points.length; i++) {
            Map<Integer,Integer> dm = new HashMap<>();
            for (int j = 0; j < points.length; j++) {
                if (i == j) continue;
                int dx = points[i][0] - points[j][0];
                int dy = points[i][1] - points[j][1];
                int d = dx * dx + dy * dy;
                dm.put(d, dm.getOrDefault(d, 0) + 1);
            }
            for (int m : dm.values()) count += m * (m - 1);
        }
        return count;
    }
}