Max Points on a Line
Return the largest number of given points that lie on one straight line.
- 1 <= points.length <= 300
- points[i].length == 2
- -10⁴ <= xi, yi <= 10⁴
- All the points are unique.
Intuition
Max points on a line asks for the largest number of given points lying on one straight line. Testing every pair as a candidate line and then rescanning all points is O(n³), and it invites a subtler bug than slowness.
The reframing that helps is to fix one point as an anchor. Every line through the anchor is identified by a direction, so the question becomes: how many other points share each direction from here? Count directions with a hash map, take the largest bucket, add one for the anchor itself, and repeat with every point as anchor. That is O(n²).
The trap is how a direction is represented. Using the slope dy / dx as a floating-point number merges lines that are nearly parallel and splits lines that should match, because binary floating point cannot represent most slopes exactly. Vertical lines divide by zero on top of that.
The fix is to keep the direction as an exact integer pair, reduced to a canonical form:
- Divide dx and dy by their greatest common divisor, then fix the sign so that opposite directions along the same line collapse to one key.
Without the sign normalisation, (1, 2) and (−1, −2) describe the same line but hash differently, splitting one line into two counts. Forcing dx non-negative — and dy non-negative when dx is zero — settles it.
A fresh map per anchor is required, since directions are only comparable relative to the same origin.
When points must be grouped by collinearity, anchor one point and group the rest by slope. Exact integer normalization is the reliable substitute for floating-point division in geometry hashing.
Approach
Before reading on: price up what the direct approach costs here, then ask what you would need to remember from the left to avoid re-scanning. Aim for O(n^2 log C) time and O(n) space.
Anchor at each point in turn
For anchor i, examine every later point j. Every line through the anchor is one direction, so counting shared directions replaces testing candidate lines — O(n²) instead of O(n³).
Reject floating-point slopes
dy / dx merges distinct lines and splits identical ones, because most slopes have no exact binary representation. Vertical lines also divide by zero. This is a correctness problem, not a precision nicety.
Reduce the direction vector
Compute dx and dy, then divide both by gcd(|dx|, |dy|). That collapses (2, 4) and (1, 2) onto the same key, since they describe the same direction at different scales.
Normalise the sign
Force dx non-negative, and when dx is zero force dy non-negative. Without this, (1, 2) and (-1, -2) hash differently despite lying on the same line, splitting one line into two counts.
Use a fresh map per anchor
Directions are only meaningful relative to their origin, so the map must be cleared for each anchor. Reusing one map across anchors would combine unrelated lines into a single count.
Add one for the anchor
The largest bucket counts points other than the anchor, so the line holds count + 1 points. Forgetting the anchor gives an answer one too small on every input.
Cost of the approach
Every anchor examines every later point with an O(log) gcd, giving O(n² log C) time and O(n) space for the per-anchor map — a solid improvement on the O(n³) triple loop, and exact rather than approximate.
Solution & live demo
Common pitfalls
Hashing floating-point slopes
slope = dy / dx
slope = (dy // g, dx // g)
Floating-point rounding can assign different keys to the same rational slope.
Leaving equivalent signs unnormalized
key = (dy // g, dx // g)
if dx < 0:
dx, dy = -dx, -dyVectors (1, 1) and (-1, -1) describe the same direction class.
Forgetting the anchor
answer = max(answer, counts[key])
answer = max(answer, counts[key] + 1)
The frequency counts other points, while the fixed anchor also lies on the line.
Edge cases
Initialize the answer to one and return it without needing a pair.
All vectors with dx == 0 are normalized to (1, 0).
Sign normalization moves the negative sign to dy, producing one shared key.