README.md

149. Max Points on a Line

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.

Example 1:

Input: points = [[1,1],[2,2],[3,3]]
Output: 3

Example 2:

Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4

Constraints:

• 1 <= points.length <= 300
• points[i].length == 2
• -104 <= xi, yi <= 104
• All the points are unique.

Solutions (Python)

1. Solution

from math import gcd


class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        ret = 1

        for i in range(len(points)):
            count = {}

            for j in range(i + 1, len(points)):
                dx = points[i][0] - points[j][0]
                dy = points[i][1] - points[j][1]

                if dx == 0:
                    k = None
                else:
                    neg = dx * dy < 0
                    dx = abs(dx)
                    dy = abs(dy)
                    g = gcd(dx, dy)
                    k = (neg, dy // g, dx // g)

                if k not in count:
                    count[k] = 1
                count[k] += 1
                ret = max(ret, count[k])

        return ret