Max Points on a Line
HardPrompt
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: 3Example 2:
Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Constraints:
1 <= points.length <= 300points[i].length == 2-104 <= xi, yi <= 104- All the
pointsare unique.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses a straightforward brute-force method. It considers every possible pair of points to define a line and then iterates through all other points to count how many are collinear with that line. This process is repeated for all pairs, and the maximum count is stored.
Algorithm
- If the number of points
nis less than or equal to 2, returnn. - Initialize a variable
maxCountto 0. - Iterate through all pairs of points
(i, j)to define a line. - For each line defined by
points[i]andpoints[j], initialize acurrentCountto 0. - Iterate through all points
kfrom0ton-1. - Check if point
kis collinear with pointsiandjusing the cross-multiplication formula. - If point
klies on the line, incrementcurrentCount. - After checking all points
k, updatemaxCount = max(maxCount, currentCount). - Return
maxCountafter all pairs(i, j)have been checked.
Walkthrough
The fundamental idea is that three points (x1, y1), (x2, y2), and (x3, y3) are collinear if the slope between (x1, y1) and (x2, y2) is the same as the slope between (x1, y1) and (x3, y3). To avoid division by zero for vertical lines and floating-point precision errors, we use the cross-multiplication form of the slope equality check: (y2 - y1) * (x3 - x1) == (y3 - y1) * (x2 - x1).
The algorithm iterates through every pair of points (i, j) to define a line. For each such line, it then performs a full scan of all points k in the dataset to count how many lie on this specific line. The maximum count found throughout this process is the result. Using long for the intermediate products in the cross-multiplication is a safeguard against potential integer overflow, although for the given constraints, int might suffice.
Here is the Java implementation:
class Solution { public int maxPoints(int[][] points) { int n = points.length; if (n <= 2) { return n; } int maxCount = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int currentCount = 0; // Define a line with points i and j, and count all points on it for (int k = 0; k < n; k++) { long x1 = points[i][0], y1 = points[i][1]; long x2 = points[j][0], y2 = points[j][1]; long x3 = points[k][0], y3 = points[k][1]; // Check if point k is collinear with i and j if ((y2 - y1) * (x3 - x1) == (y3 - y1) * (x2 - x1)) { currentCount++; } } maxCount = Math.max(maxCount, currentCount); } } return maxCount; }}Complexity
Time
O(N^3)
Space
O(1)
Trade-offs
Pros
Simple to conceptualize and implement.
Avoids floating-point arithmetic, making it robust against precision issues.
Cons
High time complexity of O(N^3), which may be too slow for larger inputs (though it might pass for N=300).
Highly redundant, as it recomputes the count for the same line multiple times for different pairs of points on that line.
Solutions
Solution
public class Solution { public int MaxPoints ( int [][] points ) { int n = points . Length ; int ans = 1 ; for ( int i = 0 ; i < n ; ++ i ) { int x1 = points [ i ][ 0 ], y1 = points [ i ][ 1 ]; for ( int j = i + 1 ; j < n ; ++ j ) { int x2 = points [ j ][ 0 ], y2 = points [ j ][ 1 ]; int cnt = 2 ; for ( int k = j + 1 ; k < n ; ++ k ) { int x3 = points [ k ][ 0 ], y3 = points [ k ][ 1 ]; int a = ( y2 - y1 ) * ( x3 - x1 ); int b = ( y3 - y1 ) * ( x2 - x1 ); if ( a == b ) { ++ cnt ; } } if ( ans < cnt ) { ans = cnt ; } } } return ans ; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.