Python O(n^2) HashMap solution


  • 1
    X

    couldn't figure out a faster way so far.

    class Solution(object):
        def numberOfBoomerangs(self, points):
            """
            :type points: List[List[int]]
            :rtype: int
            """
            if len(points) < 3:
                return 0
            res = 0
            for i in range(len(points)):
                pDict = {}
                for j in range(len(points)):
                    if j == i:
                        continue
                    dis = pow(points[i][0] - points[j][0], 2) + pow(points[i][1] - points[j][1], 2)
                    key = str(dis)
                    if key in pDict:
                        pDict[key] += 1
                    else:
                        pDict[key] = 1
                for p in pDict:
                    if pDict[p] > 1:
                        res += pDict[p] * (pDict[p] - 1)
            return res
    

  • 0
    M
    This post is deleted!

  • 0

    said in Python O(n^2) HashMap solution:

    abs

    No need to use abs() because you use pow() after it. No matter points[i][0] - points[j][0] is positive or negative the result of pow() will be the same.


  • 0

    said in Python O(n^2) HashMap solution:

                if j == i:
                    continue
    

    No need to skip the case of j==i since it will be a rare case. The number of points is up to 500. Your code only improve one single point out of 499 points.


  • 3

    Shorter version:

    class Solution(object):
        def numberOfBoomerangs(self, points):
            """
            :type points: List[List[int]]
            :rtype: int
            """
            res = 0
            for x1, y1 in points:
                cnt = {}
                for x2,y2 in points:
                    dist = (x1-x2)**2+(y1-y2)**2
                    cnt[dist] = cnt.get(dist,0) + 1
                for k in cnt:
                    res += cnt[k]*(cnt[k]-1)
            return res
    

Log in to reply
 

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