# LeetCode 447: Number of Boomerangs

## Problem Restatement

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

Each point is represented as:

```python
[x, y]
```

A boomerang is an ordered tuple of points:

```python
(i, j, k)
```

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

The order matters. So:

```python
(i, j, k)
```

and:

```python
(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

| Item | Meaning |
|---|---|
| Input | `points`, a list of distinct 2D points |
| Output | Number of boomerang tuples |
| Center point | The first point `i` |
| Condition | `distance(i, j) == distance(i, k)` |
| Order | `(i, j, k)` and `(i, k, j)` are different |

Example function shape:

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

## Examples

Example 1:

```python
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:

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

Answer:

```python
2
```

Example 2:

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

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

Answer:

```python
2
```

Example 3:

```python
points = [[1, 1]]
```

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

Answer:

```python
0
```

## First Thought: Check Every Triple

A direct approach is to try every ordered triple:

```python
(i, j, k)
```

Then check whether:

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

This works, but it takes:

```python
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:

| Position | Choices |
|---|---:|
| `j` | `m` |
| `k` | `m - 1` |

So this distance group contributes:

```python
m * (m - 1)
```

boomerangs.

We should use squared distance instead of real distance.

For points:

```python
(x1, y1)
(x2, y2)
```

the squared distance is:

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

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

## Algorithm

Initialize:

```python
answer = 0
```

For each point `i` as the center:

1. Create an empty hash map:

```python
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:

```python
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:

```python
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

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n^2)` | For each center, we scan all points |
| Space | `O(n)` | The distance map can store up to `n` distances for one center |

Here, `n` is the number of points.

## Implementation

```python
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:

```python
for x1, y1 in points:
```

For that center, we count distances:

```python
distance_count = defaultdict(int)
```

For every point:

```python
for x2, y2 in points:
```

we compute squared distance:

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

Then we count how many points share that distance:

```python
distance_count[dist] += 1
```

For each distance group with size `count`, we add:

```python
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:

```python
1 * 0 = 0
```

so it does not affect the answer.

## Testing

```python
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:

| Test | Why |
|---|---|
| Three points on a line | Checks standard example |
| Diagonal line | Checks squared distance with both coordinates |
| Single point | Checks too few points |
| Four points around center | Checks many equal-distance points |
| Diamond shape | Checks multiple centers with equal distances |