Solution by <644367822>


  • 0
    6

    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 .

Log in to reply
 

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