Max Points on a Line

Approach: Slope Hashing

For each point, calculate the slope to every other point. Use a hash map to count how many points share the same slope relative to the starting point. To avoid floating point precision issues, represent the slope as a reduced fraction (dy/gcd, dx/gcd). Keep track of the maximum count.

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

        def gcd(a, b):
            while b:
                a, b = b, a % b
            return a

        max_points = 0
        for i in range(len(points)):
            slopes = defaultdict(int)
            x1, y1 = points[i]
            for j in range(i + 1, len(points)):
                x2, y2 = points[j]
                dy, dx = y2 - y1, x2 - x1
                g = gcd(dy, dx)
                slope = (dy // g, dx // g)
                slopes[slope] += 1

            if slopes:
                max_points = max(max_points, max(slopes.values()) + 1)

        return max_points