Given an array points where points[i] = [x, y] is a point on the plane, return the maximum number of points that lie on the same straight line.
No two points in the input are the same. A single point, or a pair of points, always counts as lying on a line.
Example
All three points sit on the line y = x.
Constraints
- 1 <= points.length <= 300
- points[i].length == 2
- -10^4 <= points[i][0], points[i][1] <= 10^4
- All points in the input are unique.
Intuition
A first pass treats every pair of points as a candidate line and, for each pair, rescans the rest of the points to count how many others fall on that same line — using the integer cross product instead of a slope, so there's no division or floating-point rounding to worry about yet.
function maxPointsOnALine(points) {
const n = points.length;
// Any 0, 1, or 2 points trivially lie on some line together.
if (n <= 2) return n;
let best = 2;
// Try every pair of points as the two points that define a candidate line.
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
const [x1, y1] = points[i];
const [x2, y2] = points[j];
let count = 2; // the pair itself already lies on its own line
// Check every other point for collinearity with this pair.
for (let k = 0; k < n; k++) {
if (k === i || k === j) continue;
const [x3, y3] = points[k];
// Cross product of (P2-P1) and (P3-P1): zero area means the three points are collinear.
const cross = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);
if (cross === 0) count++;
}
if (count > best) best = count; // remember the largest line seen so far
}
}
return best;
}This checks every pair as a candidate line, then rescans all the other points for each pair — O(n³) time. It never has to worry about slope precision, but pairs (i, j) and (i, j') both re-derive everything about point i from scratch. Can we do better?
Key observation: fix one point as a "focal point" and look at the slope from it to every other point. Points that share that slope with the focal point are exactly the points collinear with it — so instead of testing pair by pair, group the other points by slope in a hash map and read the biggest group straight off. That's the same hash map grouping idea behind frequency-counting problems generally, just keyed by slope instead of by value.
The slope can't be a floating-point dy/dx, though — nearby-but-distinct fractions can collide, or worse, fail to collide when they should, due to rounding. So the key is the reduced (dy, dx) pair, cut down by their gcd, with a fixed sign convention (dx non-negative, or dx === 0 forced to a dedicated vertical-line key) so equivalent fractions like (2, -4) and (-1, 2) always land in the same bucket.
In the stored solution these read as slopeCounts (the hash map for the current focal point), localBest (its biggest bucket), and best (the running max across every focal point) — the walkthrough below builds exactly that map, one other point at a time, from a single focal point's point of view.
Walking it through:
focal point (0,0) — slope to each other point, bucketed by reduced (dy, dx)
Reduce the rise and run to (0,0) by their gcd instead of dividing — an integer key, so no rounding to worry about. Start its bucket at 1.
(3,6) has completely different raw rise and run than (2,4), but the same reduced slope — exactly the collision a float dy/dx could miss. Bucket (2,1) grows to 2.
(0,5) shares the focal point's x-coordinate — an undefined slope, so it gets its own reserved key instead of dividing by zero.
(-1,2) doesn't match the leading bucket at all — a genuinely different line through the focal point, so it starts a bucket of its own instead of joining the winner.
The biggest bucket holds (2,4) and (3,6); adding the focal point itself gives 3 collinear points. The full algorithm repeats this scan with every point as the focal point and keeps the largest result across all of them.
Optimization
Slope hashing from each focal point
Fix each point in turn as a "focal point" and compute the slope from it to every other point. Points sharing a slope from the same focal point are collinear with it, so counting slopes in a hash map and taking the max (+1 for the focal point itself) finds the best line through that focal point. The overall answer is the best count across all focal points.
The slope can't be a floating-point dy/dx — nearby-but-distinct fractions can collide or fail to collide due to precision. Instead, reduce (dy, dx) by their gcd to a canonical integer pair, fixing a sign convention (keep dx non-negative, or dx === 0 with dy forced positive for vertical lines) so (2, -4) and (-1, 2) normalize to the same key.
O(n²) time (a slope pass from each of n focal points), O(n) space for the slope map.
function maxPointsOnALine(points) {
const n = points.length;
// Any 0, 1, or 2 points trivially lie on some line together.
if (n <= 2) return n;
// Euclidean gcd, used to reduce a (dy, dx) slope to its canonical integer form.
const gcd = (a, b) => {
a = Math.abs(a);
b = Math.abs(b);
while (b !== 0) [a, b] = [b, a % b];
return a;
};
let best = 1;
// Treat every point in turn as the "focal point" the candidate lines pass through.
for (let i = 0; i < n; i++) {
// Fresh bucket per focal point: counts of "how many other points share this slope".
const slopeCounts = new Map();
let localBest = 0;
const [x1, y1] = points[i];
for (let j = 0; j < n; j++) {
if (j === i) continue; // never compare the focal point to itself
let dy = points[j][1] - y1;
let dx = points[j][0] - x1;
if (dx === 0) {
dy = 1; // vertical line sentinel: (1, 0) — avoids dividing by zero
} else {
// Reduce to lowest terms so equal ratios always produce the same key,
// instead of a float dy/dx that can round differently for equal slopes.
const g = gcd(dy, dx);
dy /= g;
dx /= g;
// Fix the sign so equivalent fractions always share a key.
if (dx < 0) {
dy = -dy;
dx = -dx;
}
}
const key = dy + "/" + dx;
const count = (slopeCounts.get(key) || 0) + 1;
slopeCounts.set(key, count);
if (count > localBest) localBest = count; // track this focal point's best bucket
}
// +1 to include the focal point itself.
if (localBest + 1 > best) best = localBest + 1;
}
return best;
}Pairwise cross product
For every pair of points, treat them as defining a candidate line and count how many of the other points are collinear with that pair using the integer cross product (x2-x1)(y3-y1) - (y2-y1)(x3-x1) === 0 (zero cross product means zero area, i.e. collinear) — no slopes or division at all. Track the best count seen across all O(n²) pairs.
O(n³) time (a full pass over points for every pair), O(1) extra space. Simpler to trust since it never computes a slope, but too slow for the largest inputs — included as a correctness cross-check, not the primary approach.
function maxPointsOnALine(points) {
const n = points.length;
// Any 0, 1, or 2 points trivially lie on some line together.
if (n <= 2) return n;
let best = 2;
// Try every pair of points as the two points that define a candidate line.
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
const [x1, y1] = points[i];
const [x2, y2] = points[j];
let count = 2; // the pair itself already lies on its own line
// Check every other point for collinearity with this pair.
for (let k = 0; k < n; k++) {
if (k === i || k === j) continue;
const [x3, y3] = points[k];
// Cross product of (P2-P1) and (P3-P1): zero area means the three points are collinear.
const cross = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);
if (cross === 0) count++;
}
if (count > best) best = count; // remember the largest line seen so far
}
}
return best;
}Complexity analysis
Time complexity: O(n²). Here's why:
- The outer loop tries each of the
npoints in turn as the focal point. - For each focal point, the inner loop visits the other
n - 1points, doing O(1) hash-map get/set work plus agcdreduction that's effectively O(1) over this problem's bounded coordinate range.
So the two nested loops multiply to O(n²) — down from the pairwise cross-product brute force's O(n³), since fixing one focal point collapses what used to be a fresh O(n) rescan for every candidate pair into a single grouping pass.
Space complexity: O(n). Here's why:
- The
slopeCountsmap holds one entry per distinct slope seen from the current focal point — up ton - 1entries if every other point sits on its own line through it. - Only one focal point's map is alive at a time; it's discarded and rebuilt fresh for the next focal point, so the maps never stack up.
So the algorithm uses O(n) auxiliary space beyond the input, not counting the handful of scalar variables (best, localBest, the loop indices).
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| points = 55 | 1 | Smallest possible input — one point trivially lies on a line by itself. |
| points = 12 34 | 2 | Any two distinct points always lie on some line together. |
| points = 00 10 01 | 2 | Smallest case where no line passes through three points — the best any pair can manage is 2. |
| points = 2-3 20 25 71 | 3 | Three points share x=2 (dx=0), exercising the vertical-line sentinel key; the fourth point sits off that line. |
| points = 00 23 46 69 | 4 | Every other point's slope from the origin reduces to 3/2 via gcd despite different raw rise/run — the integer key merges them into one bucket instead of drifting apart the way a float slope could. |
Try it yourself
Write your solution against the real judge before checking the reference.