## Algorithm

Problem Name: 149. Max Points on a Line

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.

Example 1:

```Input: points = [[1,1],[2,2],[3,3]]
Output: 3
```

Example 2:

```Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
```

Constraints:

• `1 <= points.length <= 300`
• `points[i].length == 2`
• `-104 <= xi, yi <= 104`
• All the `points` are unique.

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
typedef struct slope_s {
int x;
int y;
int n;
struct slope_s *next;
} slope_t;
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
int maxPoints(struct Point* points, int pointsSize) {
int i, j, k, s, v, m;
int x, y, d;
slope_t *list, *tail, *buff, *node;

m = 0;
list = tail = buff = NULL;
for (i = 0; i  <  pointsSize; i ++) {
k = s = v = 0;
if (tail != NULL) tail->next = buff;
buff = list;
list = tail = NULL;
for (j = i + 1; j  <  pointsSize; j ++) {
x = points[j].x - points[i].x;
y = points[j].y - points[i].y;
if (x == 0) {
if (points[j].y == points[i].y) {
s ++;
} else {
v ++;
}
} else {
d = gcd(y, x); // greatest common divider
x = x / d;
y = y / d;
node = list;
while (node && (node->x != x || node->y != y)) node = node-> next;
if (node) node->n ++;
else {
if (buff) {
node = buff;
buff = buff->next;
} else {
node = malloc(sizeof(slope_t));
//assert(node);
}
node->x = x;
node->y = y;
node->n = 1;
if (!tail) {  // first node of the list
node->next = NULL;  // cut if off from buff
list = tail = node;
} else {
node->next = list;  // chain it to the list
list = node;
}
}
}
}
if (k  <  v + s) k = v + s;
node = list;
while (node) {
if (k  <  node->n + s) k = node->n + s;
node = node->next;
}
k ++;

if (m  <  k) m = k;
}

while (list) {
node = list;
list = list->next;
free(node);
}

while (buff) {
node = buff;
buff = buff->next;
free(node);
}

return m;
}
``````
Copy The Code &

Input

cmd
points = [[1,1],[2,2],[3,3]]

Output

cmd
3

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int maxPoints(int[][] points) {
int max = 0;
for (int i = 0; i  <  points.length - 1; i++) {
Map map = new HashMap<>();
for (int j = i + 1; j  <  points.length; j++) {
double slope = calculateSlope(points[i], points[j]);
map.put(slope, map.getOrDefault(slope, 0) + 1);
max = Math.max(max, map.get(slope));
}
}
return max + 1;
}

private double calculateSlope(int[] p1, int[] p2) {
double y = (p2[1] - p1[1]) * 1.0;
double x = (p2[0] - p1[0]) * 1.0;
if (x == 0) {
return Double.NaN;
}
if(y == 0) {
return 0.0;
}
return ((double) y * 1.0) / x;
}
}
``````
Copy The Code &

Input

cmd
points = [[1,1],[2,2],[3,3]]

Output

cmd
3

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const maxPoints = function (points) {
if (points.length < 2 || points == null) return points.length
let max = 2
for (let i = 0; i  <  points.length; i++) {
let [p1x, p1y] = points[i]
let samePoint = 1,
map = { base: 0 } // to avoid when map = {}, the max value is -Infinity
for (let j = i + 1; j  <  points.length; j++) {
if (points[i][0] == points[j][0] && points[i][1] == points[j][1]) {
samePoint++
} else {
let [p2x, p2y] = points[j]
let slope = (1000000.0 * (p2y - p1y)) / (p2x - p1x)
if (!Number.isFinite(slope)) slope = 'v'
else if (Number.isNaN(slope)) slope = 'h'
map[slope] = map[slope] + 1 || 1
}
}
max = Math.max(Math.max(...Object.values(map)) + samePoint, max)
}
return max
}
``````
Copy The Code &

Input

cmd
points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]

Output

cmd
4

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def maxPoints(self, points):
m, res, roots = {}, 0, set()
for i, p1 in enumerate(points):
if (p1.x, p1.y) not in roots:
m.clear()
dup = path = 0
for j, p2 in enumerate(points):
if i != j:
try:
cur = (p1.y - p2.y) * 100 / (p1.x - p2.x)
except:
if p1.y == p2.y:
dup += 1
continue
else:
cur = "ver"
m[cur] = m.get(cur, 0) + 1
if m[cur] > path:
path = m[cur]
if path + dup + 1 > res:
res = path + dup + 1
return res
``````
Copy The Code &

Input

cmd
points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]

Output

cmd
4