#447

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Number of Boomerangs

Compute all valid boomerang tuples in a point set using array scanning with hash maps to track distances efficiently.

Problem Statement

You are given n distinct points in a 2D plane represented as points[i] = [xi, yi]. A boomerang is defined as a tuple (i, j, k) such that the distance from point i to point j equals the distance from point i to point k. The order of points in the tuple matters, meaning (i, j, k) is different from (i, k, j).

Your task is to return the total number of boomerangs present in the given point set. Each point may serve as the pivot i, and you must efficiently compute matching distances for all pairs to count every valid tuple.

Examples

Example 1

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

Output: 2

The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]].

Example 2

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

Output: 2

Example details omitted.

Example 3

Input: points = [[1,1]]

Output: 0

Example details omitted.

Constraints

n == points.length
1 <= n <= 500
points[i].length == 2
-104 <= xi, yi <= 104
All the points are unique.

Solution Approach

Iterate with Pivot Point

Loop through each point as the pivot i. For each pivot, calculate the squared distance to all other points. Squared distance avoids unnecessary square roots and preserves correctness for equality checks.

Use Hash Map for Distance Counting

Store the frequency of each distance in a hash map while scanning the array. For each distance that appears more than once, compute the number of boomerangs using count * (count - 1) to account for ordering in tuples.

Aggregate Boomerang Count

Sum the counts from all pivot points to get the total number of boomerangs. This approach reduces redundant computations and handles up to 500 points efficiently using O(n^2) time and O(n) extra space per pivot.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n^2) because each point is used as a pivot and distances are computed to all other points. Space complexity is O(n) for the hash map storing distances per pivot point.

What Interviewers Usually Probe

They may hint at optimizing distance calculations using squared distances instead of square roots.
Expect clarifying questions about handling duplicate distances efficiently with hash maps.
They may ask about edge cases such as a single point or collinear points where boomerangs are limited.

Common Pitfalls or Variants

Common pitfalls

Calculating Euclidean distance with square roots can introduce floating point errors; always use squared distance.
Failing to multiply frequency by (frequency - 1) for ordering of tuples will give incorrect counts.
Resetting the hash map incorrectly between pivot points can mix distances and produce wrong totals.

Follow-up variants

Counting boomerangs in 3D points instead of 2D using the same array scanning plus hash lookup pattern.
Finding boomerangs where distances satisfy a specific ratio rather than equality.
Modifying the problem to return all boomerang tuples explicitly instead of just the count.

FAQ

What is the most efficient approach to solve Number of Boomerangs?

Use each point as a pivot and compute distances to all other points with a hash map to count frequencies, then sum count*(count-1) for each distance.

Why use squared distances instead of actual distances?

Squared distances avoid floating point errors and expensive square root calculations while preserving equality checks required for boomerangs.

Can this approach handle large point sets efficiently?

Yes, with n up to 500, using O(n^2) time and O(n) space per pivot is feasible and avoids redundant distance recalculations.

How does the hash map improve performance in this pattern?

It allows counting all points at the same distance from the pivot in O(1) per insertion, efficiently computing permutations for boomerangs.

What common mistakes should I avoid in Number of Boomerangs?

Avoid using square roots, miscounting tuple orders, and forgetting to reset the distance map between pivot points.

terminal

Solution

Solution 1: Enumeration + Counting

We can enumerate each point in `points` as the boomerang's point $i$, and then use a hash table $cnt$ to record the number of times the distance from other points to $i$ appears.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        ans = 0
        for p1 in points:
            cnt = Counter()
            for p2 in points:
                d = dist(p1, p2)
                ans += cnt[d]
                cnt[d] += 1
        return ans << 1

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        ans = 0
        for p1 in points:
            cnt = Counter()
            for p2 in points:
                d = dist(p1, p2)
                ans += cnt[d]
                cnt[d] += 1
        return ans << 1

Continue Practicing

#391 perfect rectangle #381 insert delete getrandom o1 duplicates allowed #380 insert delete getrandom o1