Max Points on a Line Medium 0 attempts
LeetCode ↗

Max Points on a Line

Medium MatrixBFSDFS LeetCode

You're given an array points, where each points[i] = [xi, yi] marks a point on the X-Y plane. Find the largest number of these points that can all sit on one common straight line.

Input Format
Implement maxPointsOnALine(points). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

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

Example 2

Input
points = [[1,1],[1,2],[1,3]]
Output
3
Constraints
  • 1 <= points.length <= 300
  • -10^4 <= xi, yi <= 10^4
  • All input points are distinct.
Test Cases (2)
Case 1
Args: [[[1,1],[2,2],[3,3]]] Expected: 3
Case 2
Args: [[[1,1],[1,2],[1,3]]] Expected: 3
Topics
MatrixBFSDFS

Approach: Slope Counting with GCD

For each point, compute slopes to all other points. Use GCD to represent slopes as reduced fractions to avoid floating-point issues. Use a hashmap to count points sharing the same slope. Track the global maximum.

javascript
function maxPointsOnALine(points) {
  if (points.length <= 2) return points.length;
  function gcd(a, b) { return b === 0 ? a : gcd(b, a % b); }
  let max = 2;
  for (let i = 0; i < points.length; i++) {
    const map = new Map();
    for (let j = i + 1; j < points.length; j++) {
      let dx = points[j][0] - points[i][0];
      let dy = points[j][1] - points[i][1];
      const g = gcd(Math.abs(dx), Math.abs(dy));
      dx /= g; dy /= g;
      if (dx < 0 || (dx === 0 && dy < 0)) { dx = -dx; dy = -dy; }
      const key = dx + "," + dy;
      map.set(key, (map.get(key) || 1) + 1);
      max = Math.max(max, map.get(key));
    }
  }
  return max;
}

Time Complexity: O(n²)

Space Complexity: O(n)

Saved in this browser only. Private to you.

JavaScript