Leetcode: Number of Boomerangs

Number of Boomerangs



Similar Problems:


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:
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]]

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


  • Solution: hashmap with hashmap as value
// Blog link: https://code.dennyzhang.com/number-of-boomerangs
// Basic Ideas: hashmap
//
// m[0] = [1:[1], 4:[2]]
// m[1] = [1:[0, 2]]
// m[2] = [1:[1], 4:[0]]
//
// Complexity: Time O(n*n), Space O(n*n)
func numberOfBoomerangs(points [][]int) int {
  res := 0
  n := len(points)
  array := make([]map[int]int, n)
  for i:= 0; i<n; i++ { array[i] = map[int]int{} }
  for i, point1 := range points {
    m := array[i]
    for j, point2 := range points {
      if i == j { continue }
      v1, v2 := point1[0]-point2[0], point1[1]-point2[1]
      m[v1*v1+v2*v2] += 1
    }
  }
  // collect results
  for _, m := range array {
    for d := range m {
      if m[d]>1 {
        res += m[d]*(m[d]-1)
      }
    }
  }
  return res
}

  • Solution: hashmap with int as value
// Blog link: https://code.dennyzhang.com/number-of-boomerangs
// Basic Ideas: hashmap
//    hashmap with value as int
// m = [1:1, 4:1]
// m = [1:2]
// m = [1:1, 4:1]
//
// Complexity: Time O(n*n), Space O(n)

func numberOfBoomerangs(points [][]int) int {
  res := 0
  for i, point1 := range points {
    m := map[int]int{}
    for j, point2 := range points {
      if i == j { continue }
      v1, v2 := point1[0]-point2[0], point1[1]-point2[1]
      m[v1*v1+v2*v2] += 1
    }
    // collect results
    for d:= range m {
        if m[d]>1 { res += m[d]*(m[d]-1)}
    }
  }
  return res
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.