Leetcode Max Points on a Line problem solution YASH PAL, 31 July 2024 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. 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; } coding problems