DSA problem
Max Points on a Line
Given an array of points where points[i] = [xi, yi] represents a point in the XY-plane, return the maximum number of points that lie on the same straight line.
A brute-force approach picks every triple of points and checks collinearity via the cross product. That is O(n^3) and is fine for n up to a few hundred but too slow for the upper limit of 300+ points combined with the global O(n^3) constant factor.
The standard O(n^2) approach pivots on each point. Fix a pivot p_i and count how many of the remaining points share the same line through p_i. Two points share a line through the pivot iff they have the same slope to the pivot. By the pigeonhole principle, the line through p_i with the most votes — plus the pivot itself — is the best line containing p_i. Taking the max over all pivots gives the answer.
Slope must be represented robustly: floating-point division loses precision and can cause distinct lines to hash to the same value. The cleanest fix is to use the reduced integer pair (dx / g, dy / g) where g = gcd(|dx|, |dy|). We also normalize the sign so that (2, 3) and (-2, -3) map to the same key — e.g., force dx > 0, or if dx == 0 force dy > 0. Duplicate points (where both dx and dy are zero) are counted separately and added to the best slope count at the end. The algorithm runs in O(n^2) time using O(n) extra space per pivot.
Examples
points = [[1,1],[2,2],[3,3]]3points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]4points = [[0,0]]1Constraints
- 1 <= points.length <= 300
- points[i].length == 2
- -10^4 <= xi, yi <= 10^4
- All the points are unique.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.