Most Lamps on One Straight Line
HardMath & Geometry
Problem
Street lamps stand at distinct integer points points[i] = [x, y]. An engineer wants to run one straight cable that passes through as many lamps as possible.
Return the largest number of lamps that lie on a single straight line.
Example 1
- Input:
- points = [[0, 0], [1, 1], [2, 2], [3, 5], [4, 1]]
- Output:
- 3
(0, 0), (1, 1) and (2, 2) lie on y = x.
Example 2
- Input:
- points = [[2, 1], [4, 4], [6, 7], [3, 3], [1, 5], [0, 0], [8, 10]]
- Output:
- 4
(2, 1), (4, 4), (6, 7) and (8, 10) all step by (2, 3).
Example 3
- Input:
- points = [[5, 5]]
- Output:
- 1
Constraints
- 1 ≤ points.length ≤ 300
- -10^4 ≤ x, y ≤ 10^4
- All points are distinct
Hint
Show the first hint
Any line through at least two lamps passes through some lamp you can treat as an anchor.
Walkthrough
How to approach it
01Clarify before coding
- Are points distinct? Yes, so every direction vector is non-zero.
- What if there is a single point? The answer is 1.
- Can lines be vertical or horizontal? Yes; the representation must handle dx = 0 and dy = 0.
02Brute force
For every pair of points, define the line through them and count how many other points are on it with a cross product test.
Cost: O(n³): 2.7 · 10^7 cross products for n = 300, borderline, and it recounts each line many times.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.