15-line python solution

  • 0

    Use GCD to handle the slope.
    Note that the sign of return value from fractions.gcd is a little different from math.gcd in python3.
    The sign of fractions.gcd(a,b) is the same as b.
    The sign of math.gcd(a,b) is always positive.

    import fractions
    from collections import defaultdict
    class Solution(object):
        def maxPoints(self, points):
            ans = 0
            for i in range(len(points)):
                p1 = points[i]
                t = defaultdict(int)
                same = 0
                for j in range(i, len(points)):
                    p2 = points[j]
                    dx, dy = p1.x - p2.x, p1.y - p2.y
                    gcd = fractions.gcd(dx, dy)
                    if gcd == 0:
                        same += 1
                        t[(dx / gcd, dy / gcd)] += 1
                ans = max(ans, max(t.values() or [0]) + same)
            return ans

Log in to reply

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