447. Number of Boomerangs
Model: qwen3.5:9b
Topics: Hash Table,Math
FAANG asked: 1
Acceptance rate: 52.5%
Problem Breakdown
We are given a list of distinct 2D points and need to count specific tuples (i, j, k). The condition is that point j must be equidistant from point i, and point k must also be equidistant from point i. Crucially, the order matters: (A, B, C) counts as a different boomerang than (A, C, B).
Inputs: A list of points where each element is [x, y].
Output: An integer representing the total count of valid tuples.
Constraints & Edge Cases:
nup to 500 (suggests or better).- Coordinates can be negative; we must use squared Euclidean distance to avoid floating-point precision issues and square root costs.
- All points are unique, so no two indices share the same coordinates. This simplifies logic regarding duplicate distances from a pivot point.
Intuition
A brute-force approach would iterate through every possible triplet (i, j, k), checking if dist(i,j) == dist(i,k) for all combinations where and . This is because we have three nested loops. Given , , which risks Time Limit Exceeded (TLE) in Python or slower languages.
We need to optimize the check for a fixed pivot i.
If we fix point i as the center of the boomerang arm:
- We calculate the distance from
ito every other pointp. - If multiple points are at the same distance from
i, say there are such points, how many valid tuples(i, j, k)can we form using these? - Since order matters and indices must be distinct (implied by unique coordinates), any pair of those points forms 2 permutations: is impossible since points are unique. So for a specific distance group with count , the number of ways to pick two distinct arms is .
- We sum this value up across all distances and then iterate through every point as the potential pivot
i.
Approach
We will use a Hash Map (Dictionary in Python) for each iteration of the outer loop to store frequency counts of squared Euclidean distances relative to the current pivot point.
- Initialize
total_boomerangs = 0. - Iterate through every index
ifrom0ton-1: a. Create an empty hash mapdist_counts. b. For every other indexj, calculate squared distance between pointsiandj. c. Increment the count for that specific distance indist_counts. - After populating counts for pivot
i, iterate through the values ofdist_counts: a. If a distance has frequency , add tototal_boomerangs. - Return
total_boomerangs.
This reduces complexity from cubic to quadratic because we group points by distance rather than checking every triplet individually.
Complexity Analysis
Time: . We have an outer loop of size and an inner loop that iterates through the remaining points for each pivot. Dictionary operations are amortized , so total time is proportional to . With , this results in roughly 250k operations, which is well within limits. Space: . The hash map stores at most entries per iteration (worst case where all points are equidistant from the pivot). We reallocate or clear it each outer loop pass, so peak memory usage scales linearly with input size.
Solution
from typing import List
class Solution:
def numberOfBoomerangs(self, points: List[List[int]]) -> int:
total_boomerangs = 0
# Iterate through every point to act as the center (pivot) of the boomerang arm
for i in range(len(points)):
pivot_x, pivot_y = points[i]
# Map distance squared -> count of points at that distance from current pivot
dist_counts = {}
# Check all other points relative to this pivot
for j in range(len(points)):
curr_x, curr_y = points[j]
# Calculate squared Euclidean distance: (x2-x1)^2 + (y2-y1)^2
# Using squared distance avoids floating point errors and sqrt cost.
dist_sq = (curr_x - pivot_x)**2 + **(curr_y - pivot_y)2
if dist_sq in dist_counts:
dist_counts[dist_sq] += 1
else:
dist_counts[dist_sq] = 1
# For each distance group, calculate permutations of picking two distinct points
for count in dist_counts.values():
total_boomerangs += count * (count - 1)
return total_boomerangs
Edge Cases Handled
- Single Point: The outer loop runs once. Inner map has only one entry with distance 0 (self). Count is 1, so
1*(1-1)adds 0 to result. Correctly returns 0. - No Equidistant Points: If for a pivot no other points share the same distance count will be 1 for all distances in map. Formula yields . Total remains correct.
- Negative Coordinates: Handled correctly by subtraction and squaring logic; Python integers handle arbitrary size preventing overflow before calculation, though standard integer types would suffice here given constraints ().