LeetCode 447: Number of Boomerangs

Problem Restatement

We are given a list of distinct points on a 2D plane.

Each point is represented as:

[x, y]

A boomerang is an ordered tuple of points:

(i, j, k)

such that the distance from i to j equals the distance from i to k.

The order matters. So:

(i, j, k)

and:

(i, k, j)

are counted as two different boomerangs.

The official problem states that a boomerang is a tuple (i, j, k) where the distance between i and j equals the distance between i and k, and the order of the tuple matters.

Input and Output

Example function shape:

def numberOfBoomerangs(points: list[list[int]]) -> int:
    ...

Examples

Example 1:

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

Use [1, 0] as the center.

Its distance to [0, 0] is 1.

Its distance to [2, 0] is also 1.

So we can form two ordered boomerangs:

([1, 0], [0, 0], [2, 0])
([1, 0], [2, 0], [0, 0])

Answer:

2

Example 2:

points = [[1, 1], [2, 2], [3, 3]]

The middle point [2, 2] is equally far from [1, 1] and [3, 3].

Answer:

2

Example 3:

points = [[1, 1]]

There are not enough points to form a tuple of three distinct points.

Answer:

0

First Thought: Check Every Triple

A direct approach is to try every ordered triple:

(i, j, k)

Then check whether:

distance(i, j) == distance(i, k)

This works, but it takes:

O(n^3)

because there are three nested choices.

We can do better by fixing the center point.

Key Insight

For a fixed center point i, all that matters is how many points are at each distance from i.

Suppose there are m points at the same distance from i.

Then we can choose:

So this distance group contributes:

m * (m - 1)

boomerangs.

We should use squared distance instead of real distance.

For points:

(x1, y1)
(x2, y2)

the squared distance is:

(x1 - x2) ** 2 + (y1 - y2) ** 2

We do not need square roots, because equal distances have equal squared distances.

Algorithm

Initialize:

answer = 0

For each point i as the center:

1. Create an empty hash map:

distance_count = {}

2. For every other point j:

   • Compute squared distance from i to j.
   • Increase the count for that distance.

3. For each distance frequency m, add:

m * (m - 1)

to the answer.

Return answer.

Correctness

Fix a center point i.

A boomerang centered at i requires two different points j and k at the same distance from i.

The algorithm groups all points by their squared distance from i. Therefore, every valid pair (j, k) for this center must come from one of these distance groups.

If a group contains m points, then there are m choices for j and m - 1 remaining choices for k. Since order matters, this gives exactly:

m * (m - 1)

boomerangs from that group.

No boomerang is counted across two different distance groups, because points from different groups have different distances from the center.

The algorithm repeats this process for every possible center point i, so every valid ordered tuple is counted exactly once, under its own first point.

Therefore, the final answer is correct.

Complexity

Here, n is the number of points.

Implementation

from collections import defaultdict

class Solution:
    def numberOfBoomerangs(self, points: list[list[int]]) -> int:
        answer = 0

        for x1, y1 in points:
            distance_count = defaultdict(int)

            for x2, y2 in points:
                dx = x1 - x2
                dy = y1 - y2
                dist = dx * dx + dy * dy

                distance_count[dist] += 1

            for count in distance_count.values():
                answer += count * (count - 1)

        return answer

Code Explanation

We try every point as the center:

for x1, y1 in points:

For that center, we count distances:

distance_count = defaultdict(int)

For every point:

for x2, y2 in points:

we compute squared distance:

dx = x1 - x2
dy = y1 - y2
dist = dx * dx + dy * dy

Then we count how many points share that distance:

distance_count[dist] += 1

For each distance group with size count, we add:

answer += count * (count - 1)

This counts ordered pairs (j, k) at the same distance from the current center.

Including the center itself creates a distance 0 group of size 1, which contributes:

1 * 0 = 0

so it does not affect the answer.

Testing

def run_tests():
    s = Solution()

    assert s.numberOfBoomerangs([[0, 0], [1, 0], [2, 0]]) == 2

    assert s.numberOfBoomerangs([[1, 1], [2, 2], [3, 3]]) == 2

    assert s.numberOfBoomerangs([[1, 1]]) == 0

    assert s.numberOfBoomerangs([[0, 0], [1, 0], [-1, 0], [0, 1], [0, -1]]) == 20

    assert s.numberOfBoomerangs([[0, 0], [1, 1], [2, 0], [1, -1]]) == 8

    print("all tests passed")

run_tests()

Test meaning: