Max Points on a Line
Hard · Geometry · Array · Hash Table · Math · Geometry
Problem
You are given a list of distinct points on a plane, each one [x, y]. Return the largest number of them that lie on one straight line.
Any line counts: horizontal, vertical or at any angle, and it does not have to pass through the origin or through the first point.
Examples
Input: points = [[1,1],[2,2],[3,3]] Output: 3
All three points are on the line y = x.
Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]] Output: 4
(1, 4), (2, 3), (3, 2) and (4, 1) are on the line x + y = 5. No other line holds more than three of the points.
Constraints
- 1 <= len(points) <= 300
- points[i] == [x, y]
- -10^4 <= x, y <= 10^4
- all points are distinct
Approaches
- Baseline: every pair, count with the cross product — time O(n³), space O(1)
Follow-up
What if points can repeat? A duplicate of the anchor has no slope, but it is on every line through the anchor. Count the anchor’s duplicates separately and add them to the best slope group, and to the answer when every point is the same.
Related problems
Start free on Cariara · Coding problems · System design studio
