O(n^2) concise solution with explanation


  • 1
    I

    For all points in array we put squared distances to all other points to a map. Then, for every distance in the map,
    we add distance*(distance -1) to result. Note that when i == j, the result is not affected.

    class Solution {
    public:
        int numberOfBoomerangs(vector<pair<int, int>>& points) {
            int res = 0;
            for(int i = 0; i < points.size(); ++i) // all possible boomerang center points
            {
                unordered_map<int, int> m;
                for(int j = 0; j < points.size(); ++j)
                {
                    int dx = points[i].first - points[j].first;
                    int dy = points[i].second - points[j].second;
                    ++m[dx*dx + dy*dy];
                }
                for(auto it = m.begin(); it != m.end(); ++it)
                   res += it->second*(it->second-1);
                
            }
            return res;
        }
    };
    

  • 1
    D

    @i9r0k How can you make the claim that "Note that when i == j, the result is not affected."? I don't understand. Please could you explain?

    I'm assuming that the input can have repeated points.


  • 1
    I

    Per problem description, all points are pairwise distinct. Claiming that the result is not affected, I mean, that I could have added " if(i == j) continue;" right before "int dx = points[i].first - points[j].first;" line. But this is not necessary since when i == j then m[0] == 1 since all points are distinct and it->second*(it->second-1) == 1*(1-1) == 0 and we add 0 to the result.


  • 0
    D

    Thanks @i9r0k -- I missed the part which said that "Given n points in the plane that are all pairwise distinct". Makes sense now.


Log in to reply
 

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