Max Points on a Line is a Hard problem whose algorithm is almost trivial — try every point as an anchor and group the others by slope — and whose difficulty is entirely in how you represent a slope. Every natural choice is wrong in a way that passes the sample tests, which is what makes it a good question.
The problem
Given points on a plane, return the maximum number of them that lie on the same straight line.
[[1,1],[2,2],[3,3]] -> 3
[[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]] -> 4
[[1,1]] -> 1
[[1,1],[1,1]] -> 2 duplicate points
[[0,0],[0,1],[0,2]] -> 3 vertical lineThe algorithm is the easy part
Any line with two or more points passes through at least one point of the set. So fix each point as an anchor, compute the slope to every other point, and count the largest group — the line through the anchor with the most companions. Take the maximum over all anchors.
for each anchor i:
slopes = {}
for each j != i:
slopes[slope(i, j)] += 1
best = max(best, 1 + max(slopes.values()))The 1 + is the anchor itself, which the map does not count. That is the whole
algorithm, and it is O(n²). Everything below is about the word slope.
Three ways to get the slope wrong
Floating point. (double)(y2 - y1) / (x2 - x1) is the obvious choice
and it is unsound as a hash key. Slopes that are mathematically equal can differ in the last bit, so
collinear points land in different buckets — and it fails silently, on large coordinates,
long after the samples pass. Division also has to special-case a vertical line, where the
denominator is zero.
An unreduced pair. Keying by (dy, dx) without reducing treats
(1,2) and (2,4) as different slopes, which they are not.
A reduced pair without a sign convention. After dividing by the GCD,
(1,2) and (-1,-2) are the same direction but different keys. Points on
opposite sides of the anchor would then be counted as two lines.
The representation that works
dy = y2 - y1, dx = x2 - x1
g = gcd(|dy|, |dx|)
dy /= g, dx /= g
if dx < 0 (or dx == 0 and dy < 0): dy = -dy, dx = -dx canonical sign
key = (dy, dx)Reduced to lowest terms, with a fixed sign convention so each direction has exactly one
representation. Exact integer arithmetic throughout — no division, no rounding, no vertical special
case, because (1, 0) is a perfectly good key.
Being able to explain why each of the three broken versions is broken is worth more here than the code. The interviewer already knows the algorithm.
Java
class Solution {
public int maxPoints(int[][] points) {
if (points.length <= 2) return points.length;
int best = 1;
for (int i = 0; i < points.length; i++) {
// Slope, as an exact reduced fraction, to every later point.
Map<String, Integer> slopes = new HashMap<>();
int localBest = 0;
int duplicates = 0;
for (int j = i + 1; j < points.length; j++) {
int dy = points[j][1] - points[i][1];
int dx = points[j][0] - points[i][0];
if (dy == 0 && dx == 0) {
duplicates++; // sits on EVERY line through the anchor
continue;
}
int g = gcd(Math.abs(dy), Math.abs(dx));
dy /= g; dx /= g;
// One representation per direction: (1,2) and (-1,-2) must agree.
if (dx < 0 || (dx == 0 && dy < 0)) { dy = -dy; dx = -dx; }
int count = slopes.merge(dy + "/" + dx, 1, Integer::sum);
localBest = Math.max(localBest, count);
}
// + the duplicates (they lie on every line) + the anchor itself
best = Math.max(best, localBest + duplicates + 1);
}
return best;
}
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}The inner loop starts at i + 1, not 0. Any line through both i and an
earlier point was already fully counted when that earlier point was the anchor, so scanning backwards
is wasted work — it halves the constant factor and changes nothing else.
Duplicates need their own counter, and this is the real trap. A point identical
to the anchor lies on every line through it, so it cannot go into a slope bucket of its own
— it has to be added to whichever group turns out to be largest. Bucket it separately and
[[0,0],[0,0],[0,1]] returns 2 when the answer is 3: all three points sit on the vertical
line x = 0.
Hence localBest + duplicates + 1 — the biggest slope group, plus every copy of
the anchor, plus the anchor. Handling duplicates first also means gcd is never called on
(0, 0), so the reduction needs no guard.
Python
from collections import defaultdict
from math import gcd
class Solution:
def maxPoints(self, points: list[list[int]]) -> int:
if len(points) <= 2:
return len(points)
best = 1
for i, (x1, y1) in enumerate(points):
slopes = defaultdict(int)
duplicates = 0
local_best = 0
for x2, y2 in points[i + 1:]:
dy, dx = y2 - y1, x2 - x1
if dy == 0 and dx == 0:
duplicates += 1 # sits on EVERY line through the anchor
continue
g = gcd(dy, dx) # math.gcd handles negatives
dy, dx = dy // g, dx // g
if dx < 0 or (dx == 0 and dy < 0):
dy, dx = -dy, -dx # canonical direction
slopes[(dy, dx)] += 1
local_best = max(local_best, slopes[(dy, dx)])
best = max(best, local_best + duplicates + 1)
return bestA tuple is hashable, so no string key is needed — the same advantage that made
Group Anagrams cleaner in Python.
math.gcd returns a non-negative result and gcd(0, 0) == 0, so the
duplicate-point case is handled without a branch.
Complexity
| Time | Space | |
|---|---|---|
| Anchor + slope map | O(n² log C) | O(n) |
| Every triple | O(n³) | O(1) |
log C is the GCD, on coordinates bounded by C — usually dropped, but
worth naming since it is the only non-obvious factor. The map is rebuilt per anchor, so space is
O(n) rather than O(n²).
There is no known sub-quadratic algorithm for this. Saying so, rather than hunting for one, is the right answer to "can you do better?".
What the interviewer is checking
- That every line through two points can be found by anchoring at one of them.
- That floating-point slopes are unsound as hash keys, and why it fails silently.
- Reducing by the GCD, and a canonical sign.
- Vertical lines, without a special case.
- Duplicate points — counted separately and added to every line, never bucketed alone.
- Fewer than three points.
- The
1 +for the anchor. - That
O(n²)is the best known bound.