Number of Boomerangs

medium array hash map math

Problem

Given n points, return the number of boomerangs — ordered triples (i, j, k) such that the distance between i and j equals the distance between i and k.

Inputpoints = [[0,0], [1,0], [2,0]]

Output2

From point (1,0): {(0,0), (2,0)} both at dist 1 → 2 ordered pairs.

points (e.g. 0,0;1,0;2,0)

def number_of_boomerangs(points):
    total = 0
    for i, (xi, yi) in enumerate(points):
        groups = {}
        for j, (xj, yj) in enumerate(points):
            if i == j: continue
            d = (xi - xj) ** 2 + (yi - yj) ** 2
            groups[d] = groups.get(d, 0) + 1
        for c in groups.values():
            total += c * (c - 1)
    return total

function numberOfBoomerangs(points) {
  let total = 0;
  for (let i = 0; i < points.length; i++) {
    const groups = new Map();
    for (let j = 0; j < points.length; j++) {
      if (i === j) continue;
      const dx = points[i][0] - points[j][0];
      const dy = points[i][1] - points[j][1];
      const d = dx * dx + dy * dy;
      groups.set(d, (groups.get(d) || 0) + 1);
    }
    for (const c of groups.values()) total += c * (c - 1);
  }
  return total;
}

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        int total = 0;
        for (int i = 0; i < points.length; i++) {
            Map<Integer, Integer> groups = 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;
                groups.merge(d, 1, Integer::sum);
            }
            for (int c : groups.values()) total += c * (c - 1);
        }
        return total;
    }
}

int numberOfBoomerangs(vector<vector<int>>& points) {
    int total = 0;
    for (int i = 0; i < (int)points.size(); i++) {
        unordered_map<int, int> groups;
        for (int j = 0; j < (int)points.size(); j++) {
            if (i == j) continue;
            int dx = points[i][0] - points[j][0];
            int dy = points[i][1] - points[j][1];
            groups[dx * dx + dy * dy]++;
        }
        for (auto& p : groups) total += p.second * (p.second - 1);
    }
    return total;
}

Explanation

A boomerang is an ordered triple (i, j, k) where i is equally far from both j and k. The smart move is to fix each point as the center i and group all the other points by how far they are from it.

For a chosen center, we walk over every other point and compute the squared distance d = dx*dx + dy*dy (squared so we avoid square roots and floating point). We tally these distances in a hash map groups, so each entry tells us how many points sit at that exact distance from the center.

If c points share the same distance from the center, the number of ordered pairs you can pick as (j, k) is c * (c - 1) (pick any first, then any different second). We add that for every distance group, then move on to the next center.

Example: points = [[0,0], [1,0], [2,0]]. With center (1,0), both (0,0) and (2,0) are at squared distance 1, so c = 2 gives 2 * 1 = 2. The other centers contribute nothing, so the total is 2.

We do a full inner pass per center, so the time is quadratic in the number of points, with the map using linear extra space.

Time: O(n²) Space: O(n)