In this Leetcode Number of Boomerangs problem solution, You are given n points in the plane that are all distinct, where points[i] = [xi, yi]. 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). Return the number of boomerangs.
Problem solution in Python.
class Solution: def numberOfBoomerangs(self, points: List[List[int]]) -> int: count = 0 for i in range(len(points)): dt_dict = dict() for j in range(len(points)): if j != i: dt = pow(points[i][0] - points[j][0], 2) + pow(points[i][1] - points[j][1], 2) count += dt_dict.get(dt, 0) dt_dict[dt] = dt_dict.get(dt, 0) + 1 return count * 2
Problem solution in Java.
class Solution { public int numberOfBoomerangs(int[][] points) { Map<Double,Integer> map = new HashMap<>(); int res = 0 ; for(int i = 0 ; i < points.length ; i++){ for(int j = 0 ; j < points.length ; j++){ if(i==j) continue; double tmp = getDis(points[i],points[j]); map.put(tmp,map.getOrDefault(tmp,0)+1); } for(double x : map.keySet()) res += map.get(x)*(map.get(x)-1); map.clear(); } return res; } public double getDis(int[] x , int[] y){ return (x[0]-y[0])*(x[0]-y[0]) + (x[1]-y[1])*(x[1]-y[1]); } }
Problem solution in C++.
class Solution { public: int numberOfBoomerangs(vector<pair<int, int>>& points) { int result=0; unordered_map<int,int> mp; for(int i=0;i<points.size();i++){ int x1=points[i].first; int y1=points[i].second; for(int j=0;j<points.size();j++){ int x2=points[j].first; int y2=points[j].second; int dis=(y2-y1)*(y2-y1)+(x2-x1)*(x2-x1); mp[dis]++; } for(unordered_map<int,int>::iterator it=mp.begin();it!=mp.end();it++) if((*it).second>1)result+=((*it).second)*((*it).second-1); mp.clear(); } return result; } };
Problem solution in C.
#define MAP_SIZE 500 struct HashMap { int count; int val; struct HashMap *next; } disHashMap[MAP_SIZE]; void addToHashMap(int key) { int slot = key % MAP_SIZE; struct HashMap *p; if (disHashMap[slot].val == key) { disHashMap[slot].count++; } else if (disHashMap[slot].val == 0) { disHashMap[slot].val = key; disHashMap[slot].count++; } else { p = &disHashMap[slot]; while (p->val != key && p->next != NULL) { p = p->next; } if (p->val == key) { p->count++; } else { p->next = (struct HashMap *)malloc(sizeof(struct HashMap)); p = p->next; p->val = key; p->count = 1; p->next = NULL; } } } int getDistance(int* a, int *b) { return abs(a[0] - b[0]) * abs(a[0] - b[0]) + abs(a[1] - b[1]) * abs(a[1] - b[1]); } int numberOfBoomerangs(int** points, int pointsRowSize, int pointsColSize) { int i, j, k; int ret = 0; struct HashMap *p, *toBeFree, *next; for (i = 0; i < pointsRowSize; i++) { for (k = 0; k < MAP_SIZE; k++) { disHashMap[k].val = 0; disHashMap[k].count = 0; disHashMap[k].next = NULL; } for (j = 0; j < pointsRowSize; j++) { if (i == j) { continue; } addToHashMap(getDistance(points[i], points[j])); } for (k = 0; k < MAP_SIZE; k++) { p = &disHashMap[k]; while (p != NULL) { if (p->count > 1) { ret += p->count * (p->count - 1); } p = p->next; } } } return ret; }