Problem URL: Max points on a line

We will calculate the slope of each pair of points. If the slope is the same, we will increase the count. If the slope is different, we will update the maximum count.

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        if len(points) <= 2:
            return len(points)

        def slope(p1: List[int], p2: List[int]) -> int:
            if p2[0]-p1[0] == 0:
                return math.inf
            return (p2[1]-p1[1]) / (p2[0]-p1[0])

        res = 0
        for i in range(len(points)):
            count = collections.defaultdict(int)
            for j in range(i+1,len(points)):
                count[slope(points[i], points[j])] += 1
            if count:
                res = max(res, max(count.values()))

        return res+1

Time complexity: O(n^2)
Space complexity: O(n)