Skip to main content

Max Points on a Line

Problem statement

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.

My solution

/**
* @param {number[][]} points
* @return {number}
*/
var maxPoints = function(points) {
if (points.length < 3) {
return points.length;
}

let maxLine = 0;

for (let i = 0; i < points.length; i++) {
const slopes = {}

for (let j = i + 1; j < points.length; j++) {
const currentSlope = slope(points[i], points[j])

slopes[currentSlope] = slopes[currentSlope] + 1 || 2;
maxLine = Math.max(maxLine, slopes[currentSlope])
}
}

return maxLine
};

function gcd(a, b) {
return b === 0 ? a : gcd(b, a % b);
}

function slope(p1, p2) {
let xDiff = p1[0] - p2[0];
let yDiff = p1[1] - p2[1];

if (xDiff === 0) {
return "vertical"
}

if (yDiff === 0) {
return "horizontal"
}

const div = gcd(xDiff, yDiff);

xDiff /= div;
yDiff /= div;

return xDiff + "/" + yDiff;
}