# Solution by <644367822>

• #### Approach #1 (Brute Force) [Time Limit Exceeded]

Algorithm

Check all the points that satisfied distance( points i , points j ) == distance( points i , points k )

c++

class Solution {
public:
int distance( pair<int,int> a , pair<int, int > b) {
//calculate   a*a + b*b    and do not sqrt() because return type is int
return (a.first-b.first)*(a.first-b.first)+( a.second- b.second )*( a.second- b.second )  ;
}
int numberOfBoomerangs(vector<pair<int, int>>& points) {
int ans =0;
for(int i=0; i<points.size() ; i++) {
for(int j=0 ; j<points.size() ; j++ ) {
for(int k=0 ; k<points.size() ; k++ ) {
//make sure satisfied distance( i , j ) == distance( i , k )  and they are distinct
if( i!=j && i!=k &&j!= k  && distance( points[i], points[j] ) == distance( points[i],points[k] ) ) {
ans++;
}
}
}
}
return ans;
}
};


Complexity Analysis

• Time complexity : $O(n^3)$.
For each point , we try to finds them by looping through the points array which takes $O(n)$ time .Therefore,
the time complexity is $O(n^3)$.
• Space complexity : $O(1)$.

#### Approach #2(Hash Table) [Accepted]

Algorithm

We optimize the above algorithms with hash table so that we can reduce a layer of loop .
In first loop we new a hash table to calculate every distance between point i and point j .
Then the question will change to a permutation question. For example, { [0,0] , [0,1] , [1,0] , [0,-1] , [-1,0] }
the first point have the same distance with other points . Now we get four points ,for a tuple of points (i, j, k) question,
we should fill these four points to the ( j , k ) -- $A_n^2 = \frac{n!}{(n-2)!}$

c++

class Solution {
public:
int distance( pair<int,int> a , pair<int, int > b) {
return (a.first-b.first)*(a.first-b.first)+( a.second- b.second )*( a.second- b.second )  ;
}
int numberOfBoomerangs(vector<pair<int, int>>& points) {
int ans =0;
for(int i=0;i<points.size();i++) {
unordered_map<int,int> hash;
for(int j=0;j<points.size() ; j++) {
if( i == j ) {
continue;
}
hash[ distance( points[i] , points[j] ) ]++;
}
for( auto it=hash.begin() ; it!= hash.end() ;it++ ) {
ans+= (it->second)*(it->second-1);
}
}
return ans;
}
};


Complexity Analysis

• Time complexity : $O(n^2)$.
Because we reduce a layer of loop so the time complexity is $O(n^2)$.
• Space complexity : $O(k)$. k is the max size of hash table .

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.