Domain 2MediumCORE

Number of Boomerangs

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).

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Hash Table#Math

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:

  • n up to 500 (suggests O(N2)O(N^2) 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 j≠ij \neq i and k≠ik \neq i. This is O(N3)O(N^3) because we have three nested loops. Given N=500N=500, N3=125,000,000N^3 = 125,000,000, 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:

  1. We calculate the distance from i to every other point p.
  2. If multiple points are at the same distance dd from i, say there are cc such points, how many valid tuples (i, j, k) can we form using these?
  3. Since order matters and indices must be distinct (implied by unique coordinates), any pair of those cc points forms 2 permutations: (j=k)(j=k) is impossible since points are unique. So for a specific distance group with count cc, the number of ways to pick two distinct arms is P(c,2)=c×(c−1)P(c, 2) = c \times (c-1).
  4. 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.

  1. Initialize total_boomerangs = 0.
  2. Iterate through every index i from 0 to n-1: a. Create an empty hash map dist_counts. b. For every other index j, calculate squared distance between points i and j. c. Increment the count for that specific distance in dist_counts.
  3. After populating counts for pivot i, iterate through the values of dist_counts: a. If a distance has frequency cc, add c×(c−1)c \times (c-1) to total_boomerangs.
  4. 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: O(N2)O(N^2). We have an outer loop of size NN and an inner loop that iterates through the remaining N−1N-1 points for each pivot. Dictionary operations are amortized O(1)O(1), so total time is proportional to N×NN \times N. With N=500N=500, this results in roughly 250k operations, which is well within limits. Space: O(N)O(N). The hash map stores at most N−1N-1 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 1×0=01 \times 0 = 0. 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 (≈8⋅108\approx 8 \cdot 10^8).