# Leetcode Max Points on a Line problem solution

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;
}
```