Formatted question description: https://leetcode.ca/all/447.html

447. Number of Boomerangs

Level

Easy

Description

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

Solution

For each point in points, calculate the distance of any other point to the current point, and store the number of points for each distance. For each distance, if there are k points, then there are k * (k - 1) boomerangs for the current point. Calculate the sum to obtain the total number of boomerangs.

• Java
• C++
• Python

• class Solution {
      public int numberOfBoomerangs(int[][] points) {
          int count = 0;
          Map<Integer, Integer> map = new HashMap<Integer, Integer>();
          int numOfPoints = points.length;
          for (int i = 0; i < numOfPoints; i++) {
              map.clear();
              int[] point1 = points[i];
              for (int j = 0; j < numOfPoints; j++) {
                  if (i == j)
                      continue;
                  int[] point2 = points[j];
                  int distanceSquare = distanceSquare(point1, point2);
                  int distanceCount = map.getOrDefault(distanceSquare, 0);
                  distanceCount++;
                  map.put(distanceSquare, distanceCount);
              }
              Set<Integer> keySet = map.keySet();
              for (int key : keySet) {
                  int distanceCount = map.get(key);
                  count += distanceCount * (distanceCount - 1);
              }
          }
          return count;
      }
  
      public int distanceSquare(int[] point1, int[] point2) {
          return (point1[0] - point2[0]) * (point1[0] - point2[0]) + (point1[1] - point2[1]) * (point1[1] - point2[1]);
      }
  }
  

• Todo
  

• class Solution(object):
    def numberOfBoomerangs(self, points):
      """
      :type points: List[List[int]]
      :rtype: int
      """
      # idea:
      # we compute the distance starting from any given point and we use a hashtable to count the number of the same distance obtained
      # once we finish counting distance for one point, we calculate the combinations = 1 * C^1_N * C^1_(N-1)
      ans = 0
      for p1 in points:
        d = {}
        for p2 in points:
          if p1 != p2:
            dist = (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2
            d[dist] = d.get(dist, 0) + 1
        for k in d:
          ans += d[k] * (d[k] - 1)
      return ans
  
  

All Problems

All Solutions