Counting Boomerangs Efficiently: Hash‑Map Solution for LeetCode 447

Problem Statement

Given an array points of n distinct points in the plane, a boomerang is an ordered tuple (i, j, k) of distinct indices such that the Euclidean distance between i and j equals the distance between i and k. The task is to count all possible boomerangs.

Algorithm – Hash‑Map Counting

For each point i treat it as the anchor. Compute the squared Euclidean distance to every other point j:

dist = (x_i - x_j) * (x_i - x_j) + (y_i - y_j) * (y_i - y_j)

Store the frequency of each distance in a hash map {dist → count}. If a particular distance occurs cnt times, it contributes cnt * (cnt - 1) ordered boomerangs (choose j and k in order). Accumulate this contribution for all distances of the current anchor, then repeat for the next anchor.

Complexity Analysis

Time: O(n²) – each of the n anchors scans the other n‑1 points.

Space: O(n) – the hash map holds at most n‑1 distance entries for a single anchor.

Reference Implementations

Java

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        int n = points.length;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            java.util.Map<Integer, Integer> map = new java.util.HashMap<>();
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                int dx = points[i][0] - points[j][0];
                int dy = points[i][1] - points[j][1];
                int dist = dx * dx + dy * dy;
                map.put(dist, map.getOrDefault(dist, 0) + 1);
            }
            for (int cnt : map.values()) {
                ans += cnt * (cnt - 1);
            }
        }
        return ans;
    }
}

C++ (C++11)

#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        int n = points.size();
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            unordered_map<int, int> cnt;
            for (int j = 0; j < n; ++j) {
                if (i == j) continue;
                int dx = points[i][0] - points[j][0];
                int dy = points[i][1] - points[j][1];
                int dist = dx * dx + dy * dy;
                ++cnt[dist];
            }
            for (auto &kv : cnt) {
                ans += kv.second * (kv.second - 1);
            }
        }
        return ans;
    }
};

Python 3

from collections import defaultdict
from typing import List

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        ans = 0
        n = len(points)
        for i in range(n):
            cnt = defaultdict(int)
            for j in range(n):
                if i == j:
                    continue
                dx = points[i][0] - points[j][0]
                dy = points[i][1] - points[j][1]
                dist = dx * dx + dy * dy
                cnt[dist] += 1
            for c in cnt.values():
                ans += c * (c - 1)
        return ans

Key Insight

Using squared distances avoids the costly sqrt operation while preserving equality comparisons. The hash‑map aggregates points at the same distance efficiently, making the solution suitable for interview constraints.