LeetCode 447 - Number of Boomerangs

LeetCode Problem 447

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Math

Solution

Problem Understanding

The problem asks us to count the number of valid boomerangs among a set of distinct 2D points.

A boomerang is defined as a tuple (i, j, k) where the distance between point i and point j is equal to the distance between point i and point k. The important detail is that the order matters. This means (i, j, k) and (i, k, j) are considered two different boomerangs if j != k.

The input is a list of points, where each point is represented as [x, y]. Every point is unique, so there are no duplicate coordinates.

The output is a single integer representing the total number of boomerangs that can be formed.

The constraints are relatively small:

• There can be at most 500 points.
• Coordinates range from -10^4 to 10^4.

Because n is only 500, an O(n^2) solution is acceptable, but an O(n^3) solution begins to approach the upper practical limits and is less desirable. This strongly suggests that we should look for a way to avoid checking every triple explicitly.

An important observation is that we do not actually need the Euclidean distance itself. Since we only care whether two distances are equal, we can compare squared distances instead. This avoids floating point operations and precision issues.

Several edge cases are important:

• A single point cannot form any boomerang.
• Two points also cannot form a boomerang because we need three distinct positions in the tuple.
• Multiple points may exist at the same distance from a center point, producing many permutations.
• Since order matters, if there are k points at the same distance from a center, the number of boomerangs contributed is k * (k - 1).

Approaches

Brute Force Approach

The most direct approach is to examine every possible ordered triple (i, j, k) and check whether:

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

There are n choices for each of the three positions, so this requires O(n^3) iterations.

This works because it explicitly checks every possible boomerang definition. However, it is inefficient because many distance computations are repeated multiple times.

For example, when checking all triples centered at a particular point i, we repeatedly recompute distances from i to other points.

Key Insight for the Optimal Solution

The critical observation is that for a fixed center point i, we only care about how many other points are at each distance from i.

Suppose for a particular center point:

• 3 points are distance 5 away
• 2 points are distance 10 away

For the group of 3 equal-distance points:

• We can pick ordered pairs (j, k) in 3 * 2 = 6 ways.

For the group of 2 equal-distance points:

• We can pick ordered pairs in 2 * 1 = 2 ways.

So instead of checking triples directly, we can:

1. Fix a center point i
2. Compute distances from i to every other point
3. Count how many times each distance appears
4. For every frequency count, add count * (count - 1)

A hash map is perfect for grouping equal distances efficiently.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(1)	Checks every ordered triple directly
Optimal	O(n²)	O(n)	Uses a hash map to group equal distances

Algorithm Walkthrough

1. Initialize a variable total_boomerangs to store the final answer.
2. Iterate through every point as the center point i.

For each center point, we want to know how many other points exist at each distance from it. 3. Create a hash map called distance_count.

The key is the squared distance from the center point.

The value is the number of points at that distance. 4. Iterate through every other point j.

Compute the squared distance:

$(x_i - x_j)^2 + (y_i - y_j)^2$

We use squared distance because equal real distances always produce equal squared distances, and this avoids unnecessary square root calculations. 5. Increment the frequency for this distance in the hash map.

After processing all points, the hash map tells us how many points share each distance from the center point. 6. Iterate through all frequencies in the hash map.

If a distance appears count times, then:

$count \times (count - 1)$

ordered boomerangs can be formed.

This works because:

• We choose one point as j
• Then another distinct point as k
• Order matters

7. Add all such contributions to the total answer.
8. Return the final count after all center points have been processed.

Why it works

For every center point i, all valid boomerangs are formed by choosing two distinct points that are equally distant from i. The hash map groups points by distance, ensuring that every valid pair is counted exactly once. Since order matters, each group of size k contributes k * (k - 1) ordered pairs. Summing these contributions across all centers produces the correct total number of boomerangs.

Python Solution

from typing import List
from collections import defaultdict

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

        for i in range(len(points)):
            distance_count = defaultdict(int)

            x1, y1 = points[i]

            for j in range(len(points)):
                if i == j:
                    continue

                x2, y2 = points[j]

                dx = x1 - x2
                dy = y1 - y2

                squared_distance = dx * dx + dy * dy

                distance_count[squared_distance] += 1

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

        return total_boomerangs

The implementation follows the algorithm directly.

The outer loop selects each point as the center point of potential boomerangs. For every center point, we create a fresh hash map named distance_count.

Inside the inner loop, we compute the squared distance from the center point to every other point. The squared distance is used instead of the real Euclidean distance because we only need equality comparisons.

Each computed distance is stored in the hash map. The map tracks how many points occur at each distance.

After processing all other points for a given center, we iterate through the frequency values in the map. If count points share the same distance, then count * (count - 1) ordered pairs can be formed.

Finally, we accumulate all contributions into total_boomerangs and return the result.

Go Solution

func numberOfBoomerangs(points [][]int) int {
    totalBoomerangs := 0

    for i := 0; i < len(points); i++ {
        distanceCount := make(map[int]int)

        x1, y1 := points[i][0], points[i][1]

        for j := 0; j < len(points); j++ {
            if i == j {
                continue
            }

            x2, y2 := points[j][0], points[j][1]

            dx := x1 - x2
            dy := y1 - y2

            squaredDistance := dx*dx + dy*dy

            distanceCount[squaredDistance]++
        }

        for _, count := range distanceCount {
            totalBoomerangs += count * (count - 1)
        }
    }

    return totalBoomerangs
}

The Go implementation mirrors the Python logic closely.

Instead of Python's defaultdict, Go uses a map[int]int. Missing keys automatically return the zero value for integers, so incrementing works naturally.

Integer overflow is not a concern here because coordinate differences are bounded by 2 * 10^4, and squaring them still fits comfortably within Go's int type.

Go slices are used directly for point storage, and the nested loops behave identically to the Python version.

Worked Examples

Example 1

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

We process each point as the center.

Center = [0,0]

Other Point	Squared Distance	Hash Map State
[1,0]	1	{1: 1}
[2,0]	4	{1: 1, 4: 1}

No distance appears more than once.

Contribution:

• 1 * 0 = 0
• 1 * 0 = 0

Total so far = 0

Center = [1,0]

Other Point	Squared Distance	Hash Map State
[0,0]	1	{1: 1}
[2,0]	1	{1: 2}

Distance 1 appears twice.

Contribution:

• 2 * 1 = 2

Total so far = 2

Center = [2,0]

Other Point	Squared Distance	Hash Map State
[0,0]	4	{4: 1}
[1,0]	1	{4: 1, 1: 1}

No repeated distances.

Final answer = 2

Example 2

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

The middle point [2,2] has equal distances to both endpoints.

Center	Equal Distance Count	Contribution
[1,1]	none	0
[2,2]	2	2
[3,3]	none	0

Final answer = 2

Example 3

points = [[1,1]]

There are no other points available.

No boomerangs can be formed.

Final answer = 0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	For each point, we compute distances to every other point
Space	O(n)	The hash map may store up to n distinct distances

The algorithm uses two nested loops over the points, producing O(n²) total distance calculations.

The hash map is recreated for each center point and can contain at most n - 1 entries in the worst case where all distances are distinct.

Test Cases

from typing import List

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        from collections import defaultdict

        total = 0

        for i in range(len(points)):
            dist_count = defaultdict(int)

            for j in range(len(points)):
                if i == j:
                    continue

                dx = points[i][0] - points[j][0]
                dy = points[i][1] - points[j][1]

                dist = dx * dx + dy * dy
                dist_count[dist] += 1

            for count in dist_count.values():
                total += count * (count - 1)

        return total

sol = Solution()

assert sol.numberOfBoomerangs([[0,0],[1,0],[2,0]]) == 2
# Basic example with one center point producing boomerangs

assert sol.numberOfBoomerangs([[1,1],[2,2],[3,3]]) == 2
# Diagonal line example

assert sol.numberOfBoomerangs([[1,1]]) == 0
# Single point cannot form boomerangs

assert sol.numberOfBoomerangs([[0,0],[1,0]]) == 0
# Two points still cannot form boomerangs

assert sol.numberOfBoomerangs([[0,0],[1,0],[-1,0],[0,1],[0,-1]]) == 20
# Multiple equal-distance neighbors around the center

assert sol.numberOfBoomerangs([[0,0],[2,0],[1,1],[1,-1]]) == 8
# Several overlapping boomerang configurations

assert sol.numberOfBoomerangs([[0,0],[0,2],[2,0],[2,2]]) == 8
# Square corners create symmetric distances

assert sol.numberOfBoomerangs([[-10000,-10000],[10000,10000],[0,0]]) == 2
# Large coordinate values

assert sol.numberOfBoomerangs([[0,0],[1,0],[2,0],[3,0]]) == 4
# Multiple centers contribute independently

Test Summary

Test	Why
[[0,0],[1,0],[2,0]]	Basic official example
[[1,1],[2,2],[3,3]]	Diagonal alignment
[[1,1]]	Minimum input size
[[0,0],[1,0]]	Not enough points
Cross-shaped configuration	Many equal distances from one center
Mixed symmetric points	Overlapping boomerang counts
Square corners	Multiple centers with equal distances
Large coordinates	Validates arithmetic safety
Four collinear points	Multiple contributing centers

Edge Cases

A single point is the smallest possible input. Since a boomerang requires three positions in the tuple, no valid configuration exists. A buggy implementation might accidentally count self-pairs or fail to handle empty distance maps correctly. This implementation avoids that issue because the inner loop skips i == j, and no distance group ever reaches size greater than one.

Two-point inputs are another important boundary case. Even though there is one distance relationship, there are still not enough distinct points to form (i, j, k). The formula count * (count - 1) naturally produces zero when count == 1, so the implementation handles this correctly without special-case logic.

A more subtle edge case occurs when many points share the same distance from a center point. For example, four surrounding points at equal distance from the center produce many ordered combinations. A common bug is forgetting that order matters and using combinations instead of permutations. This implementation correctly uses count * (count - 1) rather than count * (count - 1) / 2, ensuring ordered tuples are counted properly.

Large coordinate values can also cause issues in some implementations if floating point distance calculations are used. By computing squared distances entirely with integers, the solution avoids precision problems and remains fully accurate even at the maximum coordinate limits.