Solution works but... Brute force, Time exceeded


  • 0
    M
    class Solution(object):
        def numberOfBoomerangs(self,points):
            """Given n points in the plane that are all pairwise distinct, a "boomerang" is a tuple of points (i, j, k)
            such that the distance between i and j equals the distance between i and k (the order of the tuple matters).
    
            Find the number of boomerangs. You may assume that n will be at most 500 and
            coordinates of points are all in the range [-10000, 10000] (inclusive).
    
            Example:
            Input:
            [[0,0],[1,0],[2,0]]
    
            Output:
            2
    
            Explanation:
            The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]
            """
    
            # points.sort()
    
            boomerangs = []
            for i in range(len(points)):
                counter1 =i+1
                while counter1 <= len(points)-2:
                    counter2=counter1+1
                    while counter2 <= len(points) - 1:
                        a = points[i]
                        b = points[counter1]
                        c = points[counter2]
                        self.isBoomarang(a, b, c, boomerangs)
                        counter2 += 1
                    counter1+=1
            return len(boomerangs)
    
        def isBoomarang(self, a, b, c, boomerangs):
            # print a, b, c
            pointABdistance =(a[0]-b[0])**2 + (a[1]-b[1])**2
            pointACdistance =(a[0]-c[0])**2 + (a[1]-c[1])**2
            pointBCdistance = (b[0] - c[0]) ** 2 + (b[1] - c[1]) ** 2
    
            if pointABdistance == pointACdistance:
                boomerangs.append([a, b, c])
                boomerangs.append([a, c, b ])
            if pointABdistance == pointBCdistance:
                boomerangs.append([b, a, c])
                boomerangs.append([b, c, a])
            if pointACdistance == pointBCdistance:
                boomerangs.append([c, b, a,])
                boomerangs.append([c, a, b])
            return (pointABdistance == pointACdistance) or  (pointBCdistance == pointACdistance) or pointABdistance == pointBCdistance
    

Log in to reply
 

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