LeetCode 149 ·
Hard
Max Points on a Line
Find the maximum number of points lying on a single straight line.
Try it
Step through the core mechanic. The simulator below runs the computational geometry shape this problem is built on.
Walk the pattern
No dedicated step-through for this one yet. The shape is Computational geometry — its pattern page has the interactive walkthrough, the reference implementation, and a five-problem progression that this problem sits inside.
The approach
For each anchor point, hash the reduced slope (Δy, Δx) by GCD to every other point; the largest bucket plus the anchor is the best line through it. Take the max over anchors.
| Aspect | Value |
|---|---|
| Pattern | Computational geometry |
| Recognise it by | Most collinear points. |
| Time complexity | O(n²) |
| Space complexity | O(n) |
| Difficulty | Hard |
Who asks it
Companies known to ask this problem, from public LeetCode company-tag aggregations. A signal of where to expect it, not a guarantee.