447. Number of Boomerangs #

Problem #

Given n points in the plane that are all pairwise distinct, a “boomerang” is a tuple of points (i, j, k) such that the distance between i and j equals the distance between i and k (the order of the tuple matters).

Find the number of boomerangs. You may assume that n will be at most 500 and coordinates of points are all in the range [-10000, 10000] (inclusive).

Example 1:

Input:
[[0,0],[1,0],[2,0]]

Output:
2

Explanation:
The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]

Problem Summary #

Given an array of Points, find the number of triples (i,j,k) such that the distance between j and i equals the distance between k and i. How many such triples are there? Note that (i,j,k) and (j,i,k) are different solutions, meaning the order of the elements matters.

Solution Approach #

This problem tests the use of hash tables.

First, compute the distances between every pair of points in turn, then record these distances in a map, where the key is the distance and the value is how many times this distance appears. Calculating distance usually requires taking a square root, but if the key is a floating-point number there may be some errors, so when calculating the distance, there is no need to take the square root in the final step; just keep the squared difference.

Finally, when computing the result, traverse the map and take out all keys whose distance is greater than 2. The corresponding value is the count, and choosing any 2 points from these counts forms a solution, so using permutations and combinations, C n 2 gives the result for this distance. Finally, accumulate all these permutation and combination results.

Code #

package leetcode

func numberOfBoomerangs(points [][]int) int {
	res := 0
	for i := 0; i < len(points); i++ {
		record := make(map[int]int, len(points))
		for j := 0; j < len(points); j++ {
			if j != i {
				record[dis(points[i], points[j])]++
			}
		}
		for _, r := range record {
			res += r * (r - 1)
		}
	}
	return res
}

func dis(pa, pb []int) int {
	return (pa[0]-pb[0])*(pa[0]-pb[0]) + (pa[1]-pb[1])*(pa[1]-pb[1])
}