8 lines Python, O(n^2) time, O(n) space, about 1000ms


  • 0
    class Solution(object):
        def numberOfBoomerangs(self, points):
            """
            :type points: List[List[int]]
            :rtype: int
            """
            ans = 0
            for x1,y1 in points:
                dic = collections.defaultdict(int)
                for x2,y2 in points:
                    dic[(x1-x2)**2 + (y1-y2)**2] += 1
                for k in dic.values():
                    ans += k*(k-1)
            return ans
    

  • 0
    L

    Can you explain the k*(k-1) step


  • 1

    @haxet
    For a given point p1 (x1, y1), the distance between p1 and any point p2 (x2, y2) is L.
    For every different distance L, dic[L*2] stores the number of all points which have same distance L from p1.
    To get a boomerang, we pick two different points from candidates, which is exactly the permutations of two elements in k elements array and equals k
    (k-1).


Log in to reply
 

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