76ms, O(n^2) runtime Python solution

  • 0

    Main algorithm:
    Compute slope for each pair and increment the counter of the same slope.

    The idea is that for each point, get the total number of points on the same line with respect to that point, and then find the max total. There's some redundant comparisons for the subsequent pairs if they are on the same line with previous points, because it should have been already accounted for in the previous iterations, but I found this solution to be easy to understand.

    def maxPoints(self, points):
        if len(points) < 2:
            return len(points)
        max_cnt = 0
        for i, p1 in enumerate(points[:-1]):
            occurence = 0
            slope_dict = {}
            for j, p2 in enumerate(points[i+1:]):
                x = p2.x - p1.x
                y = p2.y - p1.y
                slope = 0 if x==0 else y*1.0/x
                increment = 1
                if x == y == 0:
                    # If two points are exactly the same
                    occurence += 1
                    increment = 0
                same_slope = slope_dict.get(slope, 1)
                slope_dict[slope] = same_slope + increment
            max_cnt = max(max_cnt, occurence + max(slope_dict.values()))
        return max_cnt

  • 0
    This post is deleted!

Log in to reply

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