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 <= 300points[i].length == 2-104 <= xi, yi <= 104- All the
pointsare 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;
}
Input
points = [[1,1],[2,2],[3,3]]
Output
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;
}
}
Input
points = [[1,1],[2,2],[3,3]]
Output
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
}
Input
points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output
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:
roots.add((p1.x, p1.y))
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
Input
points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output
4