Max Points on a Line Medium 0 attempts
LeetCode ↗

Max Points on a Line

Medium MatrixBFSDFS LeetCode

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
Sample Input
—
Sample Output
—
Constraints
  • 1 <= points.length <= 300
  • -10^4 <= xi, yi <= 10^4
Test Cases
Case 1
Args: [[[1,1],[2,2],[3,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.

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