public int numberOfBoomerangs(int[][] points) {
int res = 0;
Map<Integer, Integer> map = new HashMap<>();
for(int i=0; i<points.length; i++) {
for(int j=0; j<points.length; j++) {
if(i == j)
continue;
int d = getDistance(points[i], points[j]);
map.put(d, map.getOrDefault(d, 0) + 1);
}
for(int val : map.values()) {
res += val * (val1);
}
map.clear();
}
return res;
}
private int getDistance(int[] a, int[] b) {
int dx = a[0]  b[0];
int dy = a[1]  b[1];
return dx*dx + dy*dy;
}
Time complexity: O(n^2)
Space complexity: O(n)
Clean java solution: O(n^2) 166ms


@asurana28 I understand the code, but could you please tell me why are we doing the val * (val1) ? I am not able to wrap my head around it.
is it the number of permutations with 2 points ? I am not able to understand. Please explain.



For every i, we capture the number of points equidistant from i. Now for this i, we have to calculate all possible permutations of (j,k) from these equidistant points.
Total number of permutations of size 2 from n different points is nP2 = n!/(n2)! = n * (n1). hope this helps.

@chidong
Using square of actual distance helps in two ways: Performance: we don't have to do extra step of taking square root
 Accuracy: we can end up having same square root values for two large consecutive numbers because of the precision limitation of datatypes float/double.


@vishal51 I did few runs and it was around 170ms for me. You can try submitting the same code.
Optimizations beyond bigO will require language specific optimizations. Like I used map.clear() instead of creating a new instance of HashMap inside the outer loop to avoid the penalty of object creation every time it enters outer loop.

@asurana28 Do you see any difference, last time I ran this gave me 1540ms...terrible !
class Solution { inline int dist(pair<int, int>& p1, pair<int, int>& p2) { int dx = p1.first  p2.first; int dy = p1.second  p2.second; return dx * dx + dy * dy; } public: int numberOfBoomerangs(vector<pair<int, int>>& points) { map<int, int> m; int ans = 0; for (auto p1 : points) { for (auto p2 : points) m[dist(p1, p2)]++; for (auto entry : m) ans += entry.second * (entry.second  1); m.clear(); } return ans; } };

@vishal51
Better to use unordered_map instead of map in c++; your code's time_complexity degraded to O(n^2 * logn) because of map. map (c++) is implemented using BST  get/set are log(n) operations
 unordered_map (c++) is implemented as hashtable  get/set are O(1) operations

@czhangaegean
This calculation is unavoidable.
Lets say the distance between i and j is d. The number of points (including j) at distance d from i could be different from the number of points (including i) at distance d from j. Thus the total number of permutations for i and j with distance d could be different.


@kawayikp
Outer loop runs n times. Both inner loops also run n times, and the statements inside both inner loops are O(1).Time complexity = O(n * 2n * 1) = O(n^2)
