Most Collinear Points

hard geometry hashing

Problem

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

Inputpoints = [[1,1],[2,2],[3,3],[1,2],[5,5]]

Output4

Anchor each point in turn. From the anchor, group the others by slope. Use a reduced (dy, dx) pair (divided by gcd, with a canonical sign) so floating point isn't needed.

points (x,y; x,y; …)

from math import gcd

def max_points(points):
    n = len(points)
    if n <= 2: return n
    best = 0
    for i in range(n):
        slopes = {}
        for j in range(n):
            if i == j: continue
            dx = points[j][0] - points[i][0]
            dy = points[j][1] - points[i][1]
            g = gcd(dx, dy) or 1
            key = (dx // g, dy // g)
            if key[0] < 0 or (key[0] == 0 and key[1] < 0):
                key = (-key[0], -key[1])
            slopes[key] = slopes.get(key, 0) + 1
        best = max(best, max(slopes.values(), default=0) + 1)
    return best

function maxPoints(points) {
  const n = points.length;
  if (n <= 2) return n;
  const gcd = (a, b) => b === 0 ? Math.abs(a) : gcd(b, a % b);
  let best = 0;
  for (let i = 0; i < n; i++) {
    const slopes = new Map();
    for (let j = 0; j < n; j++) {
      if (i === j) continue;
      let dx = points[j][0] - points[i][0];
      let dy = points[j][1] - points[i][1];
      const g = gcd(dx, dy) || 1;
      dx /= g; dy /= g;
      if (dx < 0 || (dx === 0 && dy < 0)) { dx = -dx; dy = -dy; }
      const key = dx + "," + dy;
      slopes.set(key, (slopes.get(key) || 0) + 1);
    }
    let m = 0;
    for (const v of slopes.values()) if (v > m) m = v;
    best = Math.max(best, m + 1);
  }
  return best;
}

class Solution {
    public int maxPoints(int[][] points) {
        int n = points.length;
        if (n <= 2) return n;
        int best = 0;
        for (int i = 0; i < n; i++) {
            Map<Long, Integer> slopes = new HashMap<>();
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                int dx = points[j][0] - points[i][0];
                int dy = points[j][1] - points[i][1];
                int g = gcd(dx, dy);
                if (g == 0) g = 1;
                dx /= g; dy /= g;
                if (dx < 0 || (dx == 0 && dy < 0)) { dx = -dx; dy = -dy; }
                long key = (long) dx * 100000 + dy;
                slopes.merge(key, 1, Integer::sum);
            }
            int m = 0;
            for (int v : slopes.values()) m = Math.max(m, v);
            best = Math.max(best, m + 1);
        }
        return best;
    }
    private int gcd(int a, int b) { return b == 0 ? Math.abs(a) : gcd(b, a % b); }
}

int maxPoints(vector<vector<int>>& points) {
    int n = points.size();
    if (n <= 2) return n;
    int best = 0;
    for (int i = 0; i < n; i++) {
        map<pair<int,int>, int> slopes;
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            int dx = points[j][0] - points[i][0];
            int dy = points[j][1] - points[i][1];
            int g = __gcd(abs(dx), abs(dy));
            if (g == 0) g = 1;
            dx /= g; dy /= g;
            if (dx < 0 || (dx == 0 && dy < 0)) { dx = -dx; dy = -dy; }
            slopes[{dx, dy}]++;
        }
        int m = 0;
        for (auto& p : slopes) m = max(m, p.second);
        best = max(best, m + 1);
    }
    return best;
}

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