Number of Boomerangs

1. Define the problem

You are given points on a plane, each written as a pair [x, y]. A boomerang is an ordered group of three different points (i, j, k) where the distance from i to j equals the distance from i to k. Return how many boomerangs there are. The group is ordered , so (i, j, k) and (i, k, j) count as two different boomerangs. Pick each point in turn as the middle point i, then count how many of the other points sit at each distance using a hash map from distance to tally. If d points share a distance, they give d times (d - 1) ordered pairs, because you choose one for j and a different one for k.

Constraints

n == points.length, 1 ≤ n ≤ 500
points_i.length == 2
-10⁴ ≤ x, y ≤ 10⁴
All points are different

Example

Inputpoints = [[0, 0], [1, 0], [2, 0]]

Output2

Explanation With [1, 0] as the anchor, both [0, 0] and [2, 0] sit at distance 1. That gives the two boomerangs ([1,0], [0,0], [2,0]) and ([1,0], [2,0], [0,0]).

2. Know the words first

In plain terms

Squared distance: The horizontal gap times itself plus the vertical gap times itself. It is used as the map key because it avoids square roots and rounding, and equal squared distances mean equal real distances.
Ordered pair: A pair where swapping the two items gives a different answer. With d points at the same distance there are d times (d - 1) ordered pairs of them.
Anchor point: The point in the middle of a boomerang, the one both distances are measured from. Every point takes a turn as the anchor.

3. Visualize the solution

One cell per distance key for the current anchor, plus the running total

d 0—

d 1—

d 4—

total0

Statusinit

Three points in a line, and no boomerangs counted yet.

What happens in this step

points = [[0,0], [1,0], [2,0]]
total = 0

The first three cells will hold distance keys for one anchor at a time.
The last cell keeps the running total.

Step 1 of 7

Steps to visualize

The first three cells are the keys of the distance map for the anchor being worked on right now.
The label is the squared distance and the value is how many points sit that far away.
The last cell is the running total of boomerangs found so far.
The map is emptied each time a new anchor is picked.
Each tally of d adds d times (d - 1) to the total.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

One cell per distance key for the current anchor, plus the running total

d 0—

d 1—

d 4—

total0

Statusinit

Three points in a line, and no boomerangs counted yet.

What happens in this step

points = [[0,0], [1,0], [2,0]]
total = 0

The first three cells will hold distance keys for one anchor at a time.
The last cell keeps the running total.

Step 1 of 7

5. Solution

Solution

solution.tsTypeScript

function numberOfBoomerangs(points) {
  let total = 0;

  for (const anchor of points) {
    const distances = new Map();

    for (const other of points) {
      const dx = anchor[0] - other[0];
      const dy = anchor[1] - other[1];
      const distance = dx * dx + dy * dy;

      distances.set(distance, (distances.get(distance) || 0) + 1);
    }

    for (const count of distances.values()) {
      total += count * (count - 1);
    }
  }

  return total;
}

Time: O(n^2)
Space: O(n)

6. Test cases

Test cases

Input	Expected	Covers
`points = [[0, 0], [1, 0], [2, 0]]`	`2`	example from the description
`points = [[1, 1], [2, 2], [3, 3]]`	`2`	points evenly spaced along a diagonal
`points = [[1, 1]]`	`0`	too few points to form any boomerang
`points = [[0, 0], [5, 5]]`	`0`	a boomerang needs three points
`points = [[0, 0], [1, 0], [-1, 0], [0, 1], [0, -1]]`	`20`	a centre point with four neighbours all at the same distance
`points = [[0, 0], [1, 0], [4, 0]]`	`0`	no anchor has two neighbours at a matching distance

Topic	Description
Hash Tables	Key-to-value lookup in average O(1) via hashing into buckets.
Valid Anagram	Decide whether two words use exactly the same letters by counting the letters of one in a hash map and spending them on the other.
Contains Duplicate	Answer whether any value repeats in an array by keeping every value seen so far in a hash set and stopping at the first repeat.
Ransom Note	Check whether one string can be built from the letters of another by counting the available letters in a hash map and spending them.
First Unique Character in a String	Find the index of the first character that never repeats, using one pass to count every character and a second pass to find it.
Group Anagrams	Group words that are rearrangements of each other by filing every word in a hash map under the sorted letters that form its signature.