52ms Python solution O(N^2) with point dedup


  • 4
    P

    Basically the same N square solution. Used a map to merge identical points to speed up the double loop.

    Running time 52 ms above 100% rest submissions in Python category (I know the float key in hash sucks :-)).

    # Definition for a point.
    # class Point(object):
    #     def __init__(self, a=0, b=0):
    #         self.x = a
    #         self.y = b
    
    class Solution(object):
        def maxPoints(self, points):
            """
            :type points: List[Point]
            :rtype: int
            """
            if len(points) == 0:
                return 0
            mm = {}
            for p in points:
                mm[(p.x,p.y)] = mm.get((p.x,p.y), 0) + 1
            P = mm.keys()    
            if len(P) == 1:
                return mm[P[0]]
            maxP = 0
            for i in xrange(len(P)-1):
                slopes,repCnt = {},1
                for j in xrange(i+1,len(P)):
                    dx,dy = P[i][0]-P[j][0],P[i][1]-P[j][1]
                    if dx == 0:
                        slope = "#"
                    elif dy == 0:
                        slope = 0
                    else:
                        slope = float(dy) / dx
                    slopes[slope] = slopes.get(slope,0) + mm[P[j]]
                maxP = max(maxP, mm[P[i]] + max(slopes.values()))
            return maxP

  • 0
    W

    This is brilliant!


Log in to reply
 

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