Number of Boomerangs

You are given n points in the plane that are all distinct, where points[i] = [xi, yi]. 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 of the tuple matters).

Return the number of boomerangs.

Example 1:

Input: points = [[0,0],[1,0],[2,0]] Output: 2 Explanation: The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]].

Example 2:

Input: points = [[1,1],[2,2],[3,3]] Output: 2

Example 3:

Input: points = [[1,1]] Output: 0

Constraints:

• n == points.length
• 1 <= n <= 500
• points[i].length == 2
• -104 <= xi, yi <= 104
• All the points are unique.

Approach: Per-Point Distance Counting

Algorithm

1. A boomerang (i, j, k) is determined by the pivot point i and two other points at equal distance from i
2. For every pivot i, count, using a hash map, how many other points share each squared distance
3. If c points are at the same distance from the pivot, they form c * (c - 1) ordered pairs (j, k)
4. Sum c * (c - 1) over all distances and all pivots
5. Return the accumulated total

Time & Space Complexity

• Time Complexity: O(n²) - for each pivot, all other points are examined
• Space Complexity: O(n) - the distance-count map for one pivot at a time

Java Implementation

import java.util.HashMap;
import java.util.Map;

public class NumberOfBoomerangs {

    public static int numberOfBoomerangs(int[][] points) {
        int total = 0;

        for (int[] p : points) {
            Map<Integer, Integer> distanceCount = new HashMap<>();
            for (int[] q : points) {
                int d = distanceSquared(p, q);
                distanceCount.put(d, distanceCount.getOrDefault(d, 0) + 1);
            }
            for (int count : distanceCount.values()) {
                total += count * (count - 1);
            }
        }
        return total;
    }

    private static int distanceSquared(int[] a, int[] b) {
        int dx = a[0] - b[0];
        int dy = a[1] - b[1];
        return dx * dx + dy * dy;
    }

    // Test method
    public static void main(String[] args) {
        int[][] points1 = {{0, 0}, {1, 0}, {2, 0}};
        System.out.println("numberOfBoomerangs([[0,0],[1,0],[2,0]]): "
                + numberOfBoomerangs(points1)); // Expected: 2

        int[][] points2 = {{1, 1}, {2, 2}, {3, 3}};
        System.out.println("numberOfBoomerangs([[1,1],[2,2],[3,3]]): "
                + numberOfBoomerangs(points2)); // Expected: 2

        int[][] points3 = {{1, 1}};
        System.out.println("numberOfBoomerangs([[1,1]]): "
                + numberOfBoomerangs(points3)); // Expected: 0
    }
}

Example Walkthrough

For points = [[0,0],[1,0],[2,0]]:

1. Pivot [0,0]: distance 1 to [1,0] (count 1), distance 4 to [2,0] (count 1) -> 1*0 + 1*0 = 0
2. Pivot [1,0]: distance 1 to both [0,0] and [2,0] (count 2) -> 2*1 = 2
3. Pivot [2,0]: distance 1 to [1,0] (count 1), distance 4 to [0,0] (count 1) -> 0
4. Total: 2 boomerangs: ([1,0],[0,0],[2,0]) and ([1,0],[2,0],[0,0])

Key Points

1. Order Matters: (i, j, k) and (i, k, j) are counted separately, hence the c * (c - 1) factor
2. Pivot Centering: Every boomerang is anchored at exactly one pivot point, so summing per pivot counts each once
3. Squared Distances: Using x^2 + y^2 avoids floating-point equality issues
4. O(n²): With n <= 500, the quadratic scan is well within limits
5. Edge Case: Fewer than 3 points or no equal-distance pairs yield zero