Python solution with dict, no set, use permutations formula


  • 0
    I

    basically what I do is for each point i, i calculate the distance to all the other points, and I store it in a hashmap. So for each point i, the key in the hashmap is a particular distance, and the value is the number of points that are that distance away from i.
    Now, say we know that X points are Y away from i, given this, we can calculate the number of boomerangs involving i and the X points by simply using permutations formula, which is:
    n!/(n-r)!r!, in our case r = 2, so it simplifies to n*(n-1).

    
    class Solution(object):
        def numberOfBoomerangs(self, points):
            """
            :type points: List[List[int]]
            :rtype: int
            """
            boomerang_cnt = 0
            for i in xrange(len(points)):
                dist_from_i = defaultdict(int)
                for j in xrange(len(points)):
                    if i != j:
                        dist_j_i = (points[i][0] - points[j][0])**2 + (points[i][1] - points[j][1])**2
                        dist_from_i[dist_j_i] += 1
                        
                for dist, num_points in dist_from_i.iteritems():
                    boomerang_cnt += num_points*(num_points - 1)
                    
            return boomerang_cnt

Log in to reply
 

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