solved 'Max Points on a Line' on leetcode https://leetcode.com/problems/max-points-on-a-line/

max_points_line.py

import collections
import itertools

# Definition for a point.
class Point:
    def __init__(self, a=0, b=0):
        self.x = a
        self.y = b


class Solution:
    """Inspired from this great answer:
    https://leetcode.com/discuss/44588/c-16ms-solution-o-n-2 ."""

    def maxPoints(self, points):
        point_counter = collections.Counter((p.x, p.y) for p in points)
        if len(point_counter) <= 2:
            # Can only be one line.
            return len(points)

        max_points = 0
        # Note that in combinations, the first point will
        # be fixed until enumerated all its pairs .
        curr_point, curr_slope_counter = None, collections.Counter()
        for p1, p2 in itertools.combinations(point_counter.iterkeys(), 2):
            if curr_point and curr_point != p1:
                # Calculate max number of points which goes pass curr_point.
                max_points_from_curr = max(curr_slope_counter.itervalues()) + \
                                       point_counter[curr_point]
                max_points = max(max_points, max_points_from_curr)
                curr_slope_counter.clear()

            (x1, y1), (x2, y2) = p1, p2
            slope = float(y2 - y1) / (x2 - x1) if x1 != x2 else 'INF'
            curr_slope_counter[slope] += point_counter[p2]
            curr_point = p1
        # Note the calculation of points for the last pair in iteration
        # (line 28-30) is omitted because when there are over 2 distinct points,
        #  the maximum always comes before reaching the last pair.
        return max_points


if __name__ == '__main__':
    sol = Solution()
    # Test cases.
    points = [Point(1, 1), Point(2, 2)]
    assert sol.maxPoints(points) == 2

    points = [Point(1, 1), Point(2, 2), Point(3, 3)]
    assert sol.maxPoints(points) == 3

    points = [Point(1, 1), Point(1, 1), Point(2, 2)]
    assert sol.maxPoints(points) == 3

    points = [Point(1, 1), Point(2, 2), Point(3, 8)]
    assert sol.maxPoints(points) == 2

    points = []
    assert sol.maxPoints(points) == 0

    raw_points = [[-230, 324], [-291, 141], [34, -2], [80, 22], [-28, -134],
                  [40, -23], [-72, -149], [0, -17], [32, -32], [-207, 288],
                  [7, 32], [-5, 0], [-161, 216], [-48, -122], [-3, 39],
                  [-40, -113], [115, -216], [-112, -464], [-72, -149],
                  [-32, -104], [12, 42], [-22, 19], [-6, -21], [-48, -122],
                  [161, -288], [16, 11], [39, 23], [39, 30], [873, -111]]
    points = [Point(x, y) for x, y in raw_points]
    assert sol.maxPoints(points) == 9