Code Logo

Number of Boomerangs

Published at24 Jul 2026
Created by
Medium 0 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
Recommendation Algorithm Flow for Number of Boomerangs

Solution Approach

For each point as anchor, compute squared distances to all other points. Use a hash map to count point frequency per distance. Sum m * (m - 1) for each distance group.

function solution(points) {
  var count = 0;
  for (var i = 0; i < points.length; i++) {
    var distMap = {};
    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 d = dx * dx + dy * dy;
      distMap[d] = (distMap[d] || 0) + 1;
    }
    for (var k in distMap) {
      var m = distMap[k];
      count += m * (m - 1);
    }
  }
  return count;
}

Time O(n²), Space 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;
    }
}