Maximum Points on a Line

Given a set of 2D points, find the maximum number of points that lie on the same straight line. This is a fundamental geometric problem with applications in computer graphics, computational geometry, and data analysis, helping to identify collinear features or patterns.

Problem Description

You are given an array of points, where points[i] = [x_i, y_i] represents the coordinates of the i-th point. Your task is to determine the largest subset of these points that are collinear (i.e., they all lie on the same straight line).

Key Requirements:

Your solution should identify the maximum number of points that can be placed on a single line.
Consider all possible lines formed by pairs of points and also lines formed by a single point (which implicitly contain only that point).

Expected Behavior:

The function should return an integer representing the maximum number of collinear points found.

Edge Cases to Consider:

No points: If the input array is empty.
One point: If the input array contains only a single point.
All points are the same: If all input points have identical coordinates.
Vertical lines: Lines where all points share the same x-coordinate.
Horizontal lines: Lines where all points share the same y-coordinate.

Examples

Example 1:

Input: [[1,1],[2,2],[3,3]]
Output: 3
Explanation: All three points lie on the line y = x.

Example 2:

Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation: The points [1,1], [3,2], [5,3] lie on the line y = 0.5x + 0.5. There are 3 such points.
However, the points [1,1], [2,3], [3,2] are not collinear.
The points [4,1], [3,2], [2,3] do not form a line.
The points [1,1], [3,2], [5,3] are on a line.
Consider the points [1,1], [3,2], [5,3]. Slope is (2-1)/(3-1) = 1/2.
Consider the points [1,1], [4,1]. Slope is (1-1)/(4-1) = 0. Horizontal line.
Consider the points [1,1], [2,3]. Slope is (3-1)/(2-1) = 2.
Consider the points [3,2], [4,1]. Slope is (1-2)/(4-3) = -1.
Consider the points [3,2], [2,3]. Slope is (3-2)/(2-3) = -1.
The line passing through [3,2] and [2,3] has slope -1.
The line passing through [1,1] and [3,2] has slope 1/2.
The line passing through [1,1] and [5,3] has slope 2/4 = 1/2.
The line passing through [3,2] and [5,3] has slope 1/2.
So, [1,1], [3,2], [5,3] are collinear. (3 points)

Let's re-examine. The points are:
(1,1)
(3,2)
(5,3)
(4,1)
(2,3)
(1,4)

Line through (1,1) and (3,2): slope = (2-1)/(3-1) = 1/2.
Line through (1,1) and (5,3): slope = (3-1)/(5-1) = 2/4 = 1/2.
Line through (3,2) and (5,3): slope = (3-2)/(5-3) = 1/2.
So, (1,1), (3,2), (5,3) are on the same line (3 points).

Line through (4,1) and (3,2): slope = (2-1)/(3-4) = 1/-1 = -1.
Line through (4,1) and (2,3): slope = (3-1)/(2-4) = 2/-2 = -1.
Line through (3,2) and (2,3): slope = (3-2)/(2-3) = 1/-1 = -1.
So, (4,1), (3,2), (2,3) are on the same line (3 points).

Line through (1,1) and (4,1): slope = (1-1)/(4-1) = 0. (Horizontal line)
Points on this line: (1,1), (4,1). (2 points)

Line through (1,1) and (2,3): slope = (3-1)/(2-1) = 2.
Line through (1,1) and (1,4): vertical line. (2 points)

Let's consider all pairs and their slopes.
Point (1,1):
- (3,2): slope 1/2
- (5,3): slope 1/2
- (4,1): slope 0
- (2,3): slope 2
- (1,4): vertical

Point (3,2):
- (5,3): slope 1/2
- (4,1): slope -1
- (2,3): slope -1
- (1,4): slope (4-2)/(1-3) = 2/-2 = -1

Point (5,3):
- (4,1): slope (1-3)/(4-5) = -2/-1 = 2
- (2,3): slope (3-3)/(2-5) = 0/-3 = 0
- (1,4): slope (4-3)/(1-5) = 1/-4 = -1/4

Point (4,1):
- (2,3): slope -1
- (1,4): slope (4-1)/(1-4) = 3/-3 = -1

Point (2,3):
- (1,4): slope (4-3)/(1-2) = 1/-1 = -1

Maximum collinear points:
Line 1: (1,1), (3,2), (5,3) -> 3 points (slope 1/2)
Line 2: (4,1), (3,2), (2,3) -> 3 points (slope -1)
Line 3: (4,1), (1,4) -> 2 points (slope -1)
Line 4: (1,1), (4,1) -> 2 points (slope 0)
Line 5: (1,1), (2,3) -> 2 points (slope 2)

Wait, the explanation states output 4. Let's re-evaluate.
The explanation for Example 2 is incorrect in the prompt. The provided input `[[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]` does **not** have 4 collinear points. The maximum is 3, as demonstrated above. For a correct example leading to output 4, consider: `[[1,1],[2,2],[3,3],[4,4]]`.

Let's assume the intended input for Example 2 was something like:
Input: `[[1,1],[2,2],[3,3],[4,5],[5,6]]`
Output: 3
Explanation: Points [1,1], [2,2], [3,3] lie on the line y = x.

If we must adhere to the original example's explanation:
For the input `[[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]`, the maximum number of collinear points is 3.
Let's assume the provided output of 4 in the prompt was a typo and the correct output for that specific input is 3.

Corrected Example 2:
Input: `[[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]`
Output: 3
Explanation: Points [1,1], [3,2], and [5,3] lie on the line with slope 1/2. Points [4,1], [3,2], and [2,3] lie on the line with slope -1. The maximum number of collinear points is 3.

Example 3:

Input: [[0,0],[0,0],[0,0]]
Output: 3
Explanation: All points are identical, so they lie on any line passing through (0,0). The maximum count is the total number of points.

Constraints

1 <= points.length <= 300
points[i].length == 2
-10^4 <= x_i, y_i <= 10^4
The coordinates of all points are unique. (This constraint is often imposed to simplify slope calculations. If not, handle duplicate points carefully.)

Notes

When calculating the slope between two points (x1, y1) and (x2, y2), be mindful of vertical lines where x1 == x2. You can represent this slope as infinity or use a special marker.
Floating-point precision issues can arise when comparing slopes. Consider using fractions (numerator and denominator) or a small tolerance (epsilon) if using floating-point numbers.
A brute-force approach might involve iterating through all pairs of points to define lines and then counting points on each line. However, optimizations are possible. Think about how to efficiently group points that lie on the same line.
Handling duplicate points requires careful consideration. If multiple points occupy the same coordinates, they should all be counted towards any line passing through that coordinate. (Note: The constraint above says coordinates are unique, so this is not an issue for this specific problem.)

Problem Description

Key Requirements:

Your solution should identify the maximum number of points that can be placed on a single line.

Consider all possible lines formed by pairs of points and also lines formed by a single point (which implicitly contain only that point).

Expected Behavior:

The function should return an integer representing the maximum number of collinear points found.

Edge Cases to Consider:

No points: If the input array is empty.

One point: If the input array contains only a single point.

All points are the same: If all input points have identical coordinates.

Vertical lines: Lines where all points share the same x-coordinate.

Horizontal lines: Lines where all points share the same y-coordinate.

Examples

Example 1:

Input: [[1,1],[2,2],[3,3]] Output: 3 Explanation: All three points lie on the line y = x.

Example 2:

Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]] Output: 4 Explanation: The points [1,1], [3,2], [5,3] lie on the line y = 0.5x + 0.5. There are 3 such points. However, the points [1,1], [2,3], [3,2] are not collinear. The points [4,1], [3,2], [2,3] do not form a line. The points [1,1], [3,2], [5,3] are on a line. Consider the points [1,1], [3,2], [5,3]. Slope is (2-1)/(3-1) = 1/2. Consider the points [1,1], [4,1]. Slope is (1-1)/(4-1) = 0. Horizontal line. Consider the points [1,1], [2,3]. Slope is (3-1)/(2-1) = 2. Consider the points [3,2], [4,1]. Slope is (1-2)/(4-3) = -1. Consider the points [3,2], [2,3]. Slope is (3-2)/(2-3) = -1. The line passing through [3,2] and [2,3] has slope -1. The line passing through [1,1] and [3,2] has slope 1/2. The line passing through [1,1] and [5,3] has slope 2/4 = 1/2. The line passing through [3,2] and [5,3] has slope 1/2. So, [1,1], [3,2], [5,3] are collinear. (3 points) Let's re-examine. The points are: (1,1) (3,2) (5,3) (4,1) (2,3) (1,4) Line through (1,1) and (3,2): slope = (2-1)/(3-1) = 1/2. Line through (1,1) and (5,3): slope = (3-1)/(5-1) = 2/4 = 1/2. Line through (3,2) and (5,3): slope = (3-2)/(5-3) = 1/2. So, (1,1), (3,2), (5,3) are on the same line (3 points). Line through (4,1) and (3,2): slope = (2-1)/(3-4) = 1/-1 = -1. Line through (4,1) and (2,3): slope = (3-1)/(2-4) = 2/-2 = -1. Line through (3,2) and (2,3): slope = (3-2)/(2-3) = 1/-1 = -1. So, (4,1), (3,2), (2,3) are on the same line (3 points). Line through (1,1) and (4,1): slope = (1-1)/(4-1) = 0. (Horizontal line) Points on this line: (1,1), (4,1). (2 points) Line through (1,1) and (2,3): slope = (3-1)/(2-1) = 2. Line through (1,1) and (1,4): vertical line. (2 points) Let's consider all pairs and their slopes. Point (1,1): - (3,2): slope 1/2 - (5,3): slope 1/2 - (4,1): slope 0 - (2,3): slope 2 - (1,4): vertical Point (3,2): - (5,3): slope 1/2 - (4,1): slope -1 - (2,3): slope -1 - (1,4): slope (4-2)/(1-3) = 2/-2 = -1 Point (5,3): - (4,1): slope (1-3)/(4-5) = -2/-1 = 2 - (2,3): slope (3-3)/(2-5) = 0/-3 = 0 - (1,4): slope (4-3)/(1-5) = 1/-4 = -1/4 Point (4,1): - (2,3): slope -1 - (1,4): slope (4-1)/(1-4) = 3/-3 = -1 Point (2,3): - (1,4): slope (4-3)/(1-2) = 1/-1 = -1 Maximum collinear points: Line 1: (1,1), (3,2), (5,3) -> 3 points (slope 1/2) Line 2: (4,1), (3,2), (2,3) -> 3 points (slope -1) Line 3: (4,1), (1,4) -> 2 points (slope -1) Line 4: (1,1), (4,1) -> 2 points (slope 0) Line 5: (1,1), (2,3) -> 2 points (slope 2) Wait, the explanation states output 4. Let's re-evaluate. The explanation for Example 2 is incorrect in the prompt. The provided input `[[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]` does **not** have 4 collinear points. The maximum is 3, as demonstrated above. For a correct example leading to output 4, consider: `[[1,1],[2,2],[3,3],[4,4]]`. Let's assume the intended input for Example 2 was something like: Input: `[[1,1],[2,2],[3,3],[4,5],[5,6]]` Output: 3 Explanation: Points [1,1], [2,2], [3,3] lie on the line y = x. If we must adhere to the original example's explanation: For the input `[[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]`, the maximum number of collinear points is 3. Let's assume the provided output of 4 in the prompt was a typo and the correct output for that specific input is 3. Corrected Example 2: Input: `[[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]` Output: 3 Explanation: Points [1,1], [3,2], and [5,3] lie on the line with slope 1/2. Points [4,1], [3,2], and [2,3] lie on the line with slope -1. The maximum number of collinear points is 3.

Example 3:

Input: [[0,0],[0,0],[0,0]] Output: 3 Explanation: All points are identical, so they lie on any line passing through (0,0). The maximum count is the total number of points.

Notes

When calculating the slope between two points (x1, y1) and (x2, y2), be mindful of vertical lines where x1 == x2. You can represent this slope as infinity or use a special marker.

Floating-point precision issues can arise when comparing slopes. Consider using fractions (numerator and denominator) or a small tolerance (epsilon) if using floating-point numbers.

A brute-force approach might involve iterating through all pairs of points to define lines and then counting points on each line. However, optimizations are possible. Think about how to efficiently group points that lie on the same line.

Handling duplicate points requires careful consideration. If multiple points occupy the same coordinates, they should all be counted towards any line passing through that coordinate. (Note: The constraint above says coordinates are unique, so this is not an issue for this specific problem.)