Problem #149: Max Points on a Line

Intuition & Strategy Breakdown

For each point, calculate slope to every other point. Use a hash map of slope fractions (dx/gcd, dy/gcd) to find max collinear points.

Python Solution

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        if n <= 2: return n
        
        def get_gcd(a, b):
            while b:
                a, b = b, a % b
            return a
        
        res = 1
        for i in range(n):
            slopes = {}
            for j in range(i + 1, n):
                dx = points[j][0] - points[i][0]
                dy = points[j][1] - points[i][1]
                g = get_gcd(dx, dy)
                slope = (dx // g, dy // g)
                slopes[slope] = slopes.get(slope, 0) + 1
                res = max(res, slopes[slope] + 1)
        return res

Java Solution

class Solution {
    public int maxPoints(int[][] points) {
        int n = points.length;
        if (n <= 2) return n;
        int res = 1;
        for (int i = 0; i < n; i++) {
            Map slopes = new HashMap<>();
            for (int j = i + 1; j < n; j++) {
                int dx = points[j][0] - points[i][0];
                int dy = points[j][1] - points[i][1];
                int g = gcd(dx, dy);
                String slope = (dx / g) + "_" + (dy / g);
                slopes.put(slope, slopes.getOrDefault(slope, 0) + 1);
                res = Math.max(res, slopes.get(slope) + 1);
            }
        }
        return res;
    }
    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}