Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Find the most points lying on a single straight line. The brute-force triple check is O(n³). The interview answer is O(n²): fix each point as an anchor, then group every other point by the *slope* of the line through it and the anchor using a hash map. Points sharing a slope through the same anchor are collinear. The crux is representing slope **exactly** — store the reduced (dy, dx) vector (divide by gcd, normalize the sign) as the key, never a floating-point division, to dodge precision bugs and vertical-line divide-by-zero.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you avoid the O(n³) triple loop by anchoring and hashing slopes, AND whether you represent slope without floating-point error — the gcd-reduced, sign-normalized vector is the real test. Vertical lines and the float-precision trap are the discriminators.
Where candidates slip
Using `(double) dy / dx` as the slope key (precision errors merge distinct lines and crash on vertical dx = 0), or forgetting to normalize the sign so `(1,2)` and `(-1,-2)` split a single line into two buckets.
How to stand out
Lead with 'fix an anchor, hash exact slopes', then immediately raise the precision issue and explain the gcd-reduce-plus-sign-normalize key. Mention vertical and horizontal lines fall out naturally, and that uniqueness lets you skip duplicate handling.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewMost points on one lineCheck every triple?YesNo, anchor + groupExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Brute Force — Check Every Triple (Cross Product)
1Hint 1Explore hintHide hint
Collinearity is a property of three points. What's the most direct way to test whether a third point lies on the line through two others?
2Hint 2Explore hintHide hint
For each pair (i, j), count how many other points k are collinear with them. Three points are collinear when the cross product of (j − i) and (k − i) is zero.
3Hint 3Explore hintHide hint
Track the maximum count over all pairs. Use the integer cross product `(jx−ix)(ky−iy) − (jy−iy)(kx−ix) == 0` to stay exact and avoid division.
A · Core idea
For every pair of points (i, j), walk every remaining point k and test whether i, j, k are collinear; count how many lie on that line and track the global maximum.
The exact collinearity test. Three points A, B, C are collinear exactly when the vectors B − A and C − A are parallel, i.e. their 2D cross product is zero: (Bx − Ax)(Cy − Ay) − (By − Ay)(Cx − Ax) == 0. This is pure integer arithmetic — no division, no floats, no divide-by-zero for vertical lines. That property is the reason to introduce the cross product early; the optimal approach will reuse the same 'compare directions exactly' idea, just bucketed.
Why it's correct but slow. Fixing a pair and scanning the rest reliably finds the line through that pair and counts its members. Doing it for all pairs guarantees we examine every possible line. But there are O(n²) pairs and each scan is O(n), so the total is O(n³). For n = 300 that's 2.7 × 10⁷ triples — it actually passes here, but it signals you missed the linear-per-anchor grouping.
The wasted work that motivates the upgrade. The triple loop recomputes the same line many times: the line through three collinear points is rediscovered from pair (A,B), pair (A,C), and pair (B,C) separately. If instead we group points by slope around a single anchor, every point on a line is counted once per anchor — collapsing the inner pair-scan into a single hashed pass and dropping a whole factor of n.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
points = [[0,0],[1,1],[2,2],[3,1]]pair (0,0)-(1,1)
start count = 2 (the pair itself)
count = 23C · Code with teaching comments
Reference implementation previewpublic int maxPoints(int[][] points) { int n = points.length; if (n <= 2) return n; int best = 2; for (int i = 0; i < n; i++) {Explore the full codeHide the full code
D · Why it works and complexityO(n³) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
The cross product is the float-free heart of all collinearity work: parallel direction vectors ⇔ zero cross product. Keep it in your back pocket — even the optimal hashed solution is just 'group points whose direction vector from the anchor is identical', which is the same parallelism test expressed as a hash key instead of a per-triple computation.
ComplexityO(n³) time, O(1) space — Three nested loops over pairs and a third point give n·n·n = O(n³). Only counters are stored → O(1) space.
E · Edge cases and pitfalls3Using a slope ratio with division here instead of the cross product — reintroduces float error and vertical-line divide-by-zero.Explore edge casesHide edge cases
Pitfalls
- Using a slope ratio with division here instead of the cross product — reintroduces float error and vertical-line divide-by-zero.
- Starting `count` at 0 or 1 instead of 2 — the anchor pair is two points.
- Forgetting the `n <= 2` guard — the loops never run and you'd return 0.
Approach 2 of 2 · Optimal
Anchor + Hash Exact Slopes (Optimal)
1Hint 1Explore hintHide hint
Any line that holds many points passes through at least one of them. So fix one point as an anchor — how do you count, in one pass, how many others share a line through it?
2Hint 2Explore hintHide hint
Two other points are on the same line through the anchor exactly when they have the same slope relative to the anchor. Bucket points by slope in a hash map; the biggest bucket + 1 (the anchor) is the best line through this anchor.
3Hint 3Explore hintHide hint
Represent slope exactly: dx = xj − xi, dy = yj − yi, divide both by gcd(dx, dy), then normalize the sign (make dx > 0; for vertical lines make dy > 0). Use that integer pair as the key — never a float.
A · Core idea
Fix each point i as an anchor. For every other point j, compute the direction vector (dx, dy) = (xj − xi, yj − yi) and reduce it to a canonical form that is identical for all points lying on the same line through the anchor. Tally these canonical slopes in a hash map; the largest bucket counts the other points on the best line through i, so that line holds bucket + 1 points (adding the anchor). The global maximum over all anchors is the answer.
Why anchoring works. Any line with m points passes through each of those m points. So when the anchor happens to be one of them, every other point on that line produces the same slope relative to the anchor and lands in the same bucket. We don't need to try every line explicitly — fixing each point as an anchor in turn guarantees that, for the maximal line, at least one of its points serves as anchor and sees all the others. That's why a single hashed pass per anchor, O(n²) total, suffices instead of the O(n³) triple scan.
Why the slope must be an exact integer vector, not a float. The naive key slope = dy / dx has two fatal flaws. First, division by zero on vertical lines where dx = 0. Second, and subtler, floating-point imprecision: most ratios (e.g. 1/3) aren't representable exactly in binary floating point, so two points that are genuinely collinear can produce slightly different double slopes and split into separate buckets — or two distinct lines can round to the same value and merge. Geometry demands exactness, so we keep the slope as the integer pair (dx, dy) and never divide into a real number.
Why reduce by the gcd. Points farther from the anchor along the same line have proportionally larger (dx, dy) — e.g. (1,2), (2,4), (3,6) all describe the same direction. Dividing both components by g = gcd(dx, dy) collapses them to the single reduced vector (1,2), so every point on that line hashes to one bucket regardless of how far out it sits. Without the gcd reduction, collinear-but-different-distance points would scatter across buckets and the count would be wrong.
Why normalize the sign. Even after gcd reduction, a direction and its opposite are the same line: (1,2) and (−1,−2) point along the same line through the anchor. To make them collide we choose one canonical orientation — force dx > 0; when dx == 0 (a vertical line) force dy > 0. Concretely, negate both components when dx < 0, or when dx == 0 && dy < 0. This guarantees (2,1) and (−2,−1) share a key and a line isn't accidentally counted as two.
Why `bucket + 1` and the `n <= 2` guard. Each bucket counts only the other points sharing that slope; the anchor itself lies on the line too, so the line's size is bucket + 1. And with n <= 2 the inner loop may never form a bucket, so we return n directly — one or two points are trivially collinear.
Why uniqueness simplifies things. Older variants allowed duplicate points, forcing a separate 'identical coordinate' counter added to every line through the anchor. Here points are guaranteed unique, so (dx, dy) is never (0, 0) for j != i and the gcd is always positive — no special duplicate bookkeeping needed.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
points = [[0,0],[1,1],[2,2],[3,1]], anchor = (0,0)Interactive diagram
Building an exact slope key
j = (1,1)From raw difference vector to a canonical hashable key: reduce by gcd, then normalize the sign.
3C · Code with teaching comments
D · Why it works and complexityO(n²) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
The whole optimisation is 'group by an exact direction'. A hash map turns the geometric question 'are these collinear with the anchor?' into 'do they hash to the same reduced vector?'. The reusable craft is the key design: gcd-reduce to make scale irrelevant, sign-normalize to make orientation irrelevant. Any time you group by a ratio or direction — parallel lines, equivalent fractions, reflection symmetry — this exact-key recipe beats floating point.
ComplexityO(n²) time, O(n) space — The outer loop fixes each of n anchors; the inner loop hashes the other ≤ n−1 points in O(1) average each → O(n²) time. Each anchor uses a fresh map of up to n−1 slope buckets → O(n) space.
E · Edge cases and pitfalls9points = [[1,1]] — n = 1 ≤ 2 → return 1 immediately.Explore edge casesHide edge cases
Edge cases handled
points = [[1,1]]n = 1 ≤ 2 → return 1 immediately.points = [[0,0],[0,5],[0,-3]]Vertical line: dx = 0 each time; sign-normalize forces dy > 0 so all share key (0,1) → returns 3.points = [[1,1],[2,1],[5,1]]Horizontal line: dy = 0; gcd reduces dx to 1, key (1,0) for all → returns 3.points = [[2,3],[3,3],[-5,3]] with opposite directionsAnchor (2,3): (3,3) gives (1,0); (−5,3) gives dx=−7→ normalize → (1,0). Same bucket → collinear, returns 3.
Pitfalls
- Keying on `(double) dy / dx` — float imprecision splits/merges lines and crashes on vertical dx = 0.
- Skipping gcd reduction — collinear points at different distances scatter into different buckets.
- Skipping sign normalization — a line splits into two buckets for its two directions.
- Forgetting `+1` for the anchor, or starting `best` such that the trivial 2-point line is missed.
- Reusing one slope map across anchors instead of resetting per anchor.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int maxPoints(int[][] points) { int n = points.length; if (n <= 2) return n; int best = 0; for (int i = 0; i < n; i++) {Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Floating-point slope key
Most ratios aren't exactly representable as doubles, so genuinely collinear points can produce different slopes (splitting a line) or distinct lines can round equal (merging them). Vertical lines also divide by zero. Use an exact integer vector key.
Explore the code comparisonHide the code comparison
Floating-point slope key
Most ratios aren't exactly representable as doubles, so genuinely collinear points can produce different slopes (splitting a line) or distinct lines can round equal (merging them). Vertical lines also divide by zero. Use an exact integer vector key.
Don't write this
double slope = (double) (points[j][1] - points[i][1])
/ (points[j][0] - points[i][0]); // NaN/Inf on dx == 0, imprecise otherwise
String key = String.valueOf(slope);Write this instead
int dx = points[j][0] - points[i][0];
int dy = points[j][1] - points[i][1];
int g = gcd(Math.abs(dx), Math.abs(dy));
dx /= g; dy /= g;
if (dx < 0 || (dx == 0 && dy < 0)) { dx = -dx; dy = -dy; }
String key = dx + "," + dy;2Forgetting to normalize the sign
After gcd reduction, (1,2) and (-1,-2) describe the same line through the anchor but hash differently, so the line is split into two undercounted buckets. Pick a canonical orientation.
Explore the code comparisonHide the code comparison
Forgetting to normalize the sign
After gcd reduction, (1,2) and (-1,-2) describe the same line through the anchor but hash differently, so the line is split into two undercounted buckets. Pick a canonical orientation.
Don't write this
g = math.gcd(dx, dy)
dx //= g
dy //= g
key = (dx, dy) # (1,2) and (-1,-2) become different keysWrite this instead
g = math.gcd(dx, dy)
dx //= g
dy //= g
if dx < 0 or (dx == 0 and dy < 0):
dx, dy = -dx, -dy
key = (dx, dy)3Forgetting the +1 for the anchor
The slope bucket only counts the *other* points sharing that direction. The anchor lies on the line too, so the line's true size is bucket + 1. Omitting it undercounts every line by one.
Explore the code comparisonHide the code comparison
Forgetting the +1 for the anchor
The slope bucket only counts the *other* points sharing that direction. The anchor lies on the line too, so the line's true size is bucket + 1. Omitting it undercounts every line by one.
Don't write this
slopes[key] = slopes.get(key, 0) + 1
best = max(best, slopes[key]) # misses the anchorWrite this instead
slopes[key] = slopes.get(key, 0) + 1
best = max(best, slopes[key] + 1) # +1 for the anchor itselfRevise
Carry the pattern into the interview
Pattern to remember
Anchor + hash slopes (reduced gcd vector) → most collinear points
Code pattern to memorize
best = 0
for i in range(n): # anchor
slopes = {}
for j in range(i+1, n):
dx, dy = x[j]-x[i], y[j]-y[i]
g = gcd(dx, dy) # non-negative
dx, dy = dx//g, dy//g
if dx < 0 or (dx == 0 and dy < 0): # canonical sign
dx, dy = -dx, -dy
slopes[(dx, dy)] += 1
best = max(best, slopes[(dx, dy)] + 1)
return best (or n if n <= 2)Rules to remember
- 1Represent slope as the reduced integer vector `(dx/g, dy/g)`, never
dy/dxas a float — floating point misjudges near-parallel lines. - 2Divide
dxanddyby their gcd so all points on one line collapse to the same key regardless of distance from the anchor. - 3Normalize the sign so
(2,1)and(-2,-1)map to one key — pickdx > 0, and for vertical lines (dx == 0) forcedy > 0. - 4Add +1 to the bucket count: the bucket counts the other points, the anchor itself completes the line.
- 5Handle
n <= 2up front — any one or two points are trivially collinear; returnn.
Use this pattern when
- 'Most collinear points' / 'points on the same line' over a set of coordinates
- You need an exact geometric relationship (collinearity, same direction) without float error
- Grouping by a normalized direction/ratio where a hash map collapses equivalents
- n is small-to-moderate so an O(n²) anchor sweep is acceptable
Choose another pattern when
- Points are already sorted along a known axis with a special structure → a tailored scan may beat O(n²)
- You need lines defined by a fixed direction only → simpler grouping, no per-anchor sweep
- Floating-point slope is 'good enough' → it isn't here; collinearity demands exact arithmetic
Interview takeaway
Max Points on a Line is the canonical 'hash an exact ratio' problem. The lesson that transfers: when grouping by a slope, fraction, or direction, never trust floats — reduce to a coprime integer pair with gcd and normalize the sign so equivalent ratios hash together. That exact-ratio trick reappears in Line Reflection, counting parallel segments, and any 'same direction' grouping.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternThe canonical 'anchor + hash an exact ratio' geometry pattern. Recognise it whenever you must group points by a slope, direction, or fraction and floating point would corrupt the comparison. The defining moves are the per-anchor sweep and the gcd-reduced, sign-normalized integer key; the same exact-key discipline powers Line Reflection, Number of Boomerangs, and Check If It Is a Straight Line.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Line ReflectionComing soonHash exact coordinates and test for a vertical axis of symmetry — same 'exact key, no floats' discipline.
- Number of BoomerangsComing soonAnchor each point and hash squared distances (exact integers) to count equidistant pairs.
- Check If It Is a Straight LineComing soonSingle line check — verify every point matches the first segment's slope via cross product.
- Minimum Area RectangleComing soonHash points into a set and enumerate diagonal corner pairs — geometry plus hashing.