Published Apr 10, 2022
[
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.
Input: points = [[1,1],[2,2],[3,3]]
Output: 3
Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
1 <= points.length <= 300points[i].length == 2-10^4 <= xi, yi <= 10^4points are unique.function maxPoints(points: number[][]): number {
if(points.length < 3) {
return points.length;
}
let res = 0;
for(let i = 0; i < points.length; i++){
const slopes: {[index: number]: number} = {Infinity: 0}
for(let j = i + 1; j < points.length; j++){
const xDiff = points[i][0] - points[j][0];
const yDiff = points[i][1] - points[j][1];
const slope = xDiff === 0 ? Infinity : yDiff/xDiff;
// same slope means more points on a line
slope in slopes ? slopes[slope]++ : slopes[slope] = 1
res = Math.max(res, slopes[slope])
}
}
// we didn't count the first point, so add 1
return res + 1;
};