149. Max Points on a Line

Hard

---

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.

from collections import defaultdict
import math

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        result = 0
        for i in range(len(points)):
            for j in range(i+1, len(points)):
                count = 0
                for k in range(len(points)):
                    count += self.check_line(points[i], points[j], points[k])
                result = max(result, count)
        return 1 if result == 0 else result
                    
    def check_line(self, p1, p2, p3):
        if (p1[0]- p3[0])*(p2[1]-p3[1]) == (p1[1]- p3[1])*(p2[0]- p3[0]):
            return 1
        else:
            return 0