Python 13 lines with explanation


  • 0
    N

    For each point, count the maximum number of points on a straight line starting from the point, i.e., by only using the point and subsequent points. You can do it in linear time by building a hash table with the slope as the key.

    Be careful with the duplicates, i.e., starting from the point p, you may see many other points with the same coordinates as p. So I use a separate variable dupcount to keep track of it. Setting it to be 1 initially is just a simple optimization to count itself.

        def maxPoints(self, points):
            n, np = len(points), 1 if points else 0
            for i in range(n):
                d, dupcount = defaultdict(int), 1
                for j in range(i+1, n):
                    if points[i].x == points[j].x and points[i].y == points[j].y:
                        dupcount += 1
                    else:
                        d[sys.maxsize if points[i].x == points[j].x else float(points[i].y - points[j].y) / (points[i].x - points[j].x)] += 1
                if d:
                    np = max(np, max(d.values()) + dupcount)
                elif dupcount > 1:
                    np = max(np, dupcount)
            return np
    

Log in to reply
 

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