Number of Boomerangs

Number of Boomerangs

What is this problem about?

The Number of Boomerangs problem gives you a list of points on a 2D plane. A boomerang is a tuple (i, j, k) where the distance from i to j equals the distance from i to k (i ≠ j ≠ k). Count all such ordered triplets. This Number of Boomerangs coding problem tests distance grouping with a hash map to count ordered pairs efficiently.

Why is this asked in interviews?

Google and Bloomberg ask this because it tests the insight that for each point as the pivot, grouping all other points by their squared distance reveals how many equidistant pairs exist. For a group of size m, the ordered pairs = m * (m-1). The array, math, and hash table interview pattern is directly demonstrated.

Algorithmic pattern used

Hash map per pivot. For each point i as the pivot: build a frequency map of squared distances to all other points. For each distance with count m, add m * (m-1) to the result (ordered pairs: choose 2 from m in order). No square root needed — compare squared distances for exact integer arithmetic.

Example explanation

Points: [[0,0],[1,0],[2,0]].

• Pivot (0,0): distances² = {1:1, 4:1}. No groups with m>1. Contribution=0.
• Pivot (1,0): distances² = {1:2}. m=2. Contribution = 2*(2-1) = 2.
• Pivot (2,0): distances² = {1:1, 4:1}. Contribution=0. Total = 2.

Common mistakes candidates make

• Using floating-point distance (square root) causing precision errors — always use squared distance.
• Computing unordered pairs C(m,2) instead of ordered pairs m*(m-1).
• Reusing the distance map across pivots (must reset for each pivot).
• Off-by-one: not including both (j,k) and (k,j) orientations (ordered pairs handle this automatically).

Interview preparation tip

Boomerang counting is a pattern where you fix one element (the pivot) and group the others by some property (here: distance). For each group of size m, count ordered pairs as m*(m-1). This "fix-and-group" technique applies to many pair-counting problems. Practice it on "count pairs with equal product," "count equidistant triplets," and similar grouping problems where the answer involves combinatorial counting within groups.