Practice/Google/Leetcode 149. Max Points on a Line

Leetcode 149. Max Points on a Line

CodingOptional

Problem

You are given an array of points on a 2D coordinate plane, where each point is represented as [x, y]. Your task is to determine the maximum number of points that can be found on a single straight line.

A straight line can be defined by any two distinct points. Your goal is to find which line passes through the most points in the given array.

Requirements

1. Return the maximum number of points that lie on the same straight line
2. Handle cases where points may form vertical lines (undefined slope)
3. Handle cases where points may overlap or coincide
4. All coordinates are integers
5. The solution should work efficiently for the given constraints

Constraints

• 1 ≤ points.length ≤ 300
• points[i].length == 2
• -10⁴ ≤ xᵢ, yᵢ ≤ 10⁴
• All points are unique (no duplicate coordinates)
• Time complexity should be O(n²) or better
• Space complexity should be O(n) or better

Examples

Example 1:

Input: points = [[1,1],[2,2],[3,3]] Output: 3 Explanation: All three points lie on the same line (y = x), so the answer is 3.

Example 2:

Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]] Output: 4 Explanation: The maximum number of collinear points is 4.

Example 3:

Input: points = [[1,1],[1,2],[1,3],[2,1],[2,2]] Output: 3 Explanation: Three points lie on the vertical line x = 1.