Max Points on a Line [Hard] — Slope HashMap

Problem Statement

Given n points on a 2D plane, return the maximum number of points that lie on the same straight line.

Input: [[1,1],[2,2],[3,3]] → Output: 3

Intuition

For each point as anchor, compute the slope to every other point as a reduced fraction (dy/gcd, dx/gcd). The most frequent slope + 1 = max collinear with anchor.

Solutions

C++

int maxPoints(vector<vector<int>>& points) {
    int n=points.size(), ans=1;
    for(int i=0;i<n;i++){
        unordered_map<string,int> cnt;
        for(int j=i+1;j<n;j++){
            int dx=points[j][0]-points[i][0], dy=points[j][1]-points[i][1];
            int g=__gcd(abs(dx),abs(dy));
            if(g==0){ans=max(ans,2);continue;}
            string key=to_string(dy/g)+"/"+to_string(dx/g);
            ans=max(ans,++cnt[key]+1);
        }
    }
    return ans;
}

Python

from collections import defaultdict
from math import gcd

def maxPoints(points: list[list[int]]) -> int:
    n = len(points)
    if n <= 2:
        return n
    ans = 1
    for i in range(n):
        slopes = defaultdict(int)
        for j in range(i+1, n):
            dx = points[j][0] - points[i][0]
            dy = points[j][1] - points[i][1]
            g = gcd(abs(dx), abs(dy))
            if g == 0:
                slopes['same'] += 1
            else:
                key = (dy // g, dx // g)
                slopes[key] += 1
        ans = max(ans, max(slopes.values()) + 1)
    return ans

Complexity

Time: O(n²)
Space: O(n)