In this Leetcode Max Points on a Line problem solution, we have Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.

Leetcode Max Points on a Line problem solution


Problem solution in Python.

def maxPoints(self, points):
        if len(points) == 0:
            return 0
        def computeGCD(x, y):   
            while(y): 
                x, y = y, x % y 
            return x 
        def create(i1, j1, i2, j2):
            if i2 == i1:
                return (float('inf'),float('inf'))
            if j2 == j1:
                return (0, 0)
            gcd = computeGCD(j2 - j1, i2 - i1)
            return ((j2 - j1)/gcd, (i2 - i1)/gcd) 
        mx = 0
        for i in range(len(points)):
            lines = defaultdict(lambda: 0)
            dup = 1
            for j in range(i+1, len(points)):
                if points[i] == points[j]:
                    dup+= 1
                else:
                    s1, s2 = create(points[i][0], points[i][1], points[j][0], points[j][1])
                    lines[(s1, s2)]+= 1
                    mx = max(mx, lines[s1, s2])
            
            mx = max(mx, dup)
            for p in lines:
                mx = max(mx, lines[p]+dup)
        return mx



Problem solution in Java.

public int maxPoints(Point[] points) {
		int max = 0;
		if (points == null || points.length == 0) return 0;
		int n = points.length;
		if (n == 1) return 1;
		for (int i = 0; i < n - 1; ++i) {
			Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
			int dup = 0, lclmax = 0;
			for (int j = i + 1; j < n; ++j) {
				int x = points[j].x - points[i].x;
				int y = points[j].y - points[i].y;
				if (x == 0 && y == 0) {
					++dup;
					continue;
				}
				int gcd = gcd(x, y);
				x /= gcd;
				y /= gcd;
				if (!map.containsKey(x)) map.put(x, new HashMap<Integer, Integer>());
				if (!map.get(x).containsKey(y)) map.get(x).put(y, 0);
				map.get(x).put(y, map.get(x).get(y) + 1);
				lclmax = Math.max(lclmax, map.get(x).get(y));
			}
			max = Math.max(max, dup + lclmax + 1);
		}
		return max;
	}
	
	private int gcd(int a, int b) {
		if (b == 0) return a;
		return gcd(b, a % b);
	}


Problem solution in C++.

int maxPoints(vector& points) {

    int n=points.size();  
    int res=0;
    unordered_map<double,int> ht;
    for(int i=0,mx,base;i<n;i++){
        mx=0; base=1; ht.clear();
        for(int j=i+1;j<n;j++){
            if(points[j].x==points[i].x&&points[j].y==points[i].y)
                base++;
            else{
                // slope of the line passing through point i and j
                double k=(points[j].x==points[i].x)?INFINITY:(points[j].y-(double)points[i].y)/(points[j].x-points[i].x);       
                mx=max(++ht[k],mx);
            }
        }
        res=max(res,mx+base);
    }
    return res;
}