Max Points on a Line
Problem Satement​
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.
Examples​
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:​
- All the points are unique.
Algorithm Explanation​
-
Input Handling:
- If there are 2 or fewer points, all points will always lie on the same line, so we can directly return the number of points.
-
Initialization:
- Initialize
maxi
to 2, since at least two points can define a line.
- Initialize
-
Iterate through each pair of points:
- Use a nested loop to select pairs of points
(i, j)
wherei < j
.
- Use a nested loop to select pairs of points
-
Count points on the line:
- For each pair
(i, j)
, initialize a count of 2 (since the pair itself constitutes two points on the line). - Check every other point
k
to see if it lies on the line defined by(i, j)
. - To determine if three points are collinear, use the slope comparison:
(y2 - y1) \times (x1 - x3) = (y1 - y3) \times (x2 - x1)
This equation avoids division and thus floating-point inaccuracies.
- For each pair
-
Update Maximum Count:
- Update
maxi
if the current line defined by points(i, j)
has more points than the previously recorded maximum.
- Update
-
Return Result:
- After checking all pairs, return the maximum number of collinear points found.
Code Implementation​
C++ Implementation​
class Solution {
public:
int maxPoints(vector<vector<int>>& points) {
int n = points.size();
if(n <= 2)
return n;
int maxi = 2;
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
int count = 2;
for(int k = 0; k < n; k++) {
if(k != i && k != j) {
if((points[j][1] - points[i][1]) * (points[i][0] - points[k][0]) ==
(points[i][1] - points[k][1]) * (points[j][0] - points[i][0])) {
count++;
}
}
}
maxi = max(maxi, count);
}
}
return maxi;
}
};
Python Implementation​
class Solution:
def maxPoints(self, points: List[List[int]]) -> int:
n = len(points)
if n <= 2:
return n
maxi = 2
for i in range(n):
for j in range(i + 1, n):
count = 2
for k in range(n):
if k != i and k != j:
if (points[j][1] - points[i][1]) * (points[i][0] - points[k][0]) == \
(points[i][1] - points[k][1]) * (points[j][0] - points[i][0]):
count += 1
maxi = max(maxi, count)
return maxi
Java Implementation​
class Solution {
public int maxPoints(int[][] points) {
int n = points.length;
if (n <= 2)
return n;
int maxi = 2;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int count = 2;
for (int k = 0; k < n; k++) {
if (k != i && k != j) {
if ((points[j][1] - points[i][1]) * (points[i][0] - points[k][0]) ==
(points[i][1] - points[k][1]) * (points[j][0] - points[i][0])) {
count++;
}
}
}
maxi = Math.max(maxi, count);
}
}
return maxi;
}
}
JavaScript Implementation​
var maxPoints = function (points) {
let n = points.length;
if (n <= 2) return n;
let maxi = 2;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
let count = 2;
for (let k = 0; k < n; k++) {
if (k !== i && k !== j) {
if (
(points[j][1] - points[i][1]) * (points[i][0] - points[k][0]) ===
(points[i][1] - points[k][1]) * (points[j][0] - points[i][0])
) {
count++;
}
}
}
maxi = Math.max(maxi, count);
}
}
return maxi;
};