Problem Description

You are given n distinct points on a 2D plane, where each point is represented as points[i] = [xi, yi].

A boomerang is defined as a tuple of three points (i, j, k) where:

• The distance from point i to point j equals the distance from point i to point k
• The order of the tuple matters (meaning (i, j, k) is different from (i, k, j))

Your task is to count the total number of boomerangs that can be formed from the given points.

For example, if you have points A, B, and C where A is equidistant from both B and C, then you can form two boomerangs: (A, B, C) and (A, C, B). Point A acts as the "pivot" point, while B and C are the two points at equal distance from A.

The key insight is that for each point that serves as the pivot (point i), you need to find all pairs of other points that are equidistant from it. If there are x points at the same distance from a pivot point, you can form x * (x - 1) boomerangs with that pivot, since you can choose any of the x points as j and any of the remaining x - 1 points as k.

Intuition

To solve this problem, we need to think about what makes a boomerang. A boomerang (i, j, k) requires point i to be equidistant from points j and k. This means point i acts as the "center" or "pivot" of the boomerang.

The key realization is that we can fix each point as the pivot point i and then look for all other points that share the same distance from it. If multiple points are at the same distance from our pivot, we can form multiple boomerangs.

For instance, if we have a pivot point i and there are 3 points (A, B, C) all at distance d from i, we can form the following boomerangs:

• (i, A, B), (i, A, C)
• (i, B, A), (i, B, C)
• (i, C, A), (i, C, B)

That's 3 × 2 = 6 boomerangs total. In general, if there are x points at the same distance from pivot i, we can choose any one as point j (x choices) and any other as point k (x-1 choices), giving us x × (x - 1) boomerangs.

The approach becomes clear: for each point as a potential pivot, we:

1. Calculate distances from this pivot to all other points
2. Group points by their distance from the pivot
3. For each group with x points at the same distance, add x × (x - 1) to our total count

We can optimize this further by using a counting technique. As we iterate through points for a fixed pivot, we can maintain a counter of distances seen so far. When we encounter a distance d that we've seen cnt[d] times before, we know we can form cnt[d] × 2 new boomerangs (the current point paired with each previous point at distance d, considering both orders).

Solution Approach

The solution implements an enumeration and counting strategy to efficiently count all boomerangs.

Algorithm Steps:

1. Initialize the answer counter to 0, which will store the total number of boomerangs.

2. Enumerate each point as the pivot - For each point p1 in the points array, treat it as the pivot point i of potential boomerangs.

3. For each pivot, create a distance counter - Initialize an empty hash table cnt using Python's Counter() to track the frequency of distances from the current pivot to other points.

4. Calculate distances and count incrementally - For each other point p2:

   • Calculate the distance d from p1 to p2 using the dist() function
   • Before updating the counter, add cnt[d] to the answer. This represents the number of boomerangs we can form with the current point p2 and all previously seen points at the same distance d
   • Increment cnt[d] by 1 to record this new point at distance d

5. Double the final result - Since each boomerang (i, j, k) is counted once when processing it as (i, j, k) and once as (i, k, j) in our incremental counting approach, but we only count one direction, we multiply the final answer by 2 using bit shift ans << 1.

Why this incremental counting works:

When we encounter a point at distance d and we've already seen cnt[d] points at this distance, we can form cnt[d] new boomerang pairs with this new point (pairing it with each of the previous points). Since order matters, each pair contributes 2 boomerangs, but our incremental approach counts each pair once from each direction, so we need to double the final result.

Time Complexity: O(n²) where n is the number of points, as we iterate through all pairs of points.

Space Complexity: O(n) for the hash table storing distance counts for each pivot point.

Example Walkthrough

Let's walk through a small example with 4 points to illustrate the solution approach:

Given points: [[0,0], [1,0], [2,0], [1,1]]

Let's label them as A(0,0), B(1,0), C(2,0), and D(1,1) for clarity.

Step 1: Use A(0,0) as pivot

• Initialize cnt = {} and process each other point:
• Distance to B(1,0): d = 1² + 0² = 1
  • cnt[1] = 0 initially, so add 0 to answer
  • Update cnt[1] = 1
• Distance to C(2,0): d = 2² + 0² = 4
  • cnt[4] = 0 initially, so add 0 to answer
  • Update cnt[4] = 1
• Distance to D(1,1): d = 1² + 1² = 2
  • cnt[2] = 0 initially, so add 0 to answer
  • Update cnt[2] = 1
• Running total: 0

Step 2: Use B(1,0) as pivot

• Initialize cnt = {} and process each other point:
• Distance to A(0,0): d = 1² + 0² = 1
  • cnt[1] = 0 initially, so add 0 to answer
  • Update cnt[1] = 1
• Distance to C(2,0): d = 1² + 0² = 1
  • cnt[1] = 1 now, so add 1 to answer (can form boomerang with A and C)
  • Update cnt[1] = 2
• Distance to D(1,1): d = 0² + 1² = 1
  • cnt[1] = 2 now, so add 2 to answer (can form boomerangs with A&D and C&D)
  • Update cnt[1] = 3
• Running total: 0 + 1 + 2 = 3

Step 3: Use C(2,0) as pivot

• Initialize cnt = {} and process each other point:
• Distance to A(0,0): d = 2² + 0² = 4
  • cnt[4] = 0 initially, so add 0 to answer
  • Update cnt[4] = 1
• Distance to B(1,0): d = 1² + 0² = 1
  • cnt[1] = 0 initially, so add 0 to answer
  • Update cnt[1] = 1
• Distance to D(1,1): d = 1² + 1² = 2
  • cnt[2] = 0 initially, so add 0 to answer
  • Update cnt[2] = 1
• Running total: 3 + 0 = 3

Step 4: Use D(1,1) as pivot

• Initialize cnt = {} and process each other point:
• Distance to A(0,0): d = 1² + 1² = 2
  • cnt[2] = 0 initially, so add 0 to answer
  • Update cnt[2] = 1
• Distance to B(1,0): d = 0² + 1² = 1
  • cnt[1] = 0 initially, so add 0 to answer
  • Update cnt[1] = 1
• Distance to C(2,0): d = 1² + 1² = 2
  • cnt[2] = 1 now, so add 1 to answer (can form boomerang with A and C)
  • Update cnt[2] = 2
• Running total: 3 + 1 = 4

Step 5: Double the result

• Final answer: 4 × 2 = 8 boomerangs

The 8 boomerangs are:

• With B as pivot and A,C equidistant: (B,A,C) and (B,C,A)
• With B as pivot and A,D equidistant: (B,A,D) and (B,D,A)
• With B as pivot and C,D equidistant: (B,C,D) and (B,D,C)
• With D as pivot and A,C equidistant: (D,A,C) and (D,C,A)

Solution Implementation

Time and Space Complexity

The time complexity is O(n^2), where n is the length of the array points. This is because we have two nested loops - the outer loop iterates through all points as p1, and for each p1, the inner loop iterates through all points as p2. This gives us n × n = n^2 iterations in total.

The space complexity is O(n), where n is the length of the array points. The space is primarily used by the Counter object cnt, which in the worst case stores distances from one point p1 to all other points. Since there are at most n unique distances from any single point to all other points (including itself), the Counter can hold at most n entries at any given time. The Counter is reset for each new p1 in the outer loop, so we only need O(n) space rather than O(n^2).

Common Pitfalls

1. Using Floating-Point Distance Calculations

The Pitfall: A common mistake is calculating the actual Euclidean distance using sqrt(), which introduces floating-point precision issues. When comparing distances, floating-point errors can cause two equal distances to be treated as different values in the hash table.

# INCORRECT - Floating point precision issues
import math
distance = math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)

The Solution: Use squared distances instead. Since we only need to check if distances are equal (not their actual values), comparing squared distances works perfectly and avoids floating-point arithmetic entirely:

# CORRECT - Use squared distance
distance = (p1[0] - p2[0])**2 + (p1[1] - p2[1])**2

2. Incorrect Counting Formula

The Pitfall: Some might try to count all boomerangs at once after collecting all distances, using the formula n * (n-1) directly:

# INCORRECT - This misses the incremental nature
for dist, count in distance_count.items():
    if count >= 2:
        total_boomerangs += count * (count - 1)

The Solution: The incremental counting approach shown in the solution is correct. When we encounter each new point at distance d, we add distance_count[d] (the number of previously seen points at this distance) to our total. This naturally accounts for all pairs.

3. Including the Center Point in Distance Calculations

The Pitfall: Forgetting that the center point will have distance 0 to itself, which shouldn't form valid boomerangs:

# This includes distance from point to itself (always 0)
for other_point in points:
    distance = calculate_distance(center_point, other_point)
    # Distance 0 when center_point == other_point

The Solution: While the code still calculates distance to itself (which is 0), this doesn't create incorrect boomerangs because:

• A single point at distance 0 won't form any boomerangs (need at least 2 points at the same distance)
• The incremental counting naturally handles this case correctly

Alternatively, you could explicitly skip the center point:

for other_point in points:
    if other_point == center_point:
        continue
    distance = calculate_distance(center_point, other_point)

4. Forgetting to Multiply by 2

The Pitfall: The incremental counting approach counts each valid pair once, but since order matters in boomerangs (i, j, k) vs (i, k, j), forgetting the final multiplication by 2 will give half the correct answer:

# INCORRECT - Missing the multiplication
return total_boomerangs  # Should be total_boomerangs * 2

The Solution: Always remember to multiply the final result by 2, as each pair of equidistant points forms 2 different boomerangs based on their ordering.