Max Points on a Line — Hard Problem & Solution

Problem statement

Given points on a plane, return the maximum number of them that lie on the same straight line.

Example 1

Input: points = [[1,1],[2,2],[3,3]]
Output: 3
Explanation: All three sit on the line y = x.

Example 2

Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation: (1,4), (2,3), (3,2) and (4,1) are collinear.

Example 3

Input: points = [[0,0]]
Output: 1

Constraints

• 1 <= points.length <= 300
• points[i].length == 2
• -10000 <= x, y <= 10000
• All points are distinct.

How to solve Max Points on a Line

Anchor on each point and bucket the other points by the reduced direction vector to it. The largest bucket plus the anchor itself is the best line through that anchor; the maximum over anchors is the answer.

Approach

1. For each anchor i, walk every other point j and form (dx, dy) = (xj - xi, yj - yi).
2. Divide both by gcd(|dx|, |dy|) so parallel vectors reduce to the same pair.
3. Flip the sign so that dx > 0, or dx == 0 with dy > 0 — this merges a direction with its opposite.
4. Tally the normalised keys; the best count plus one (for the anchor) is a candidate answer.

Why it works

Two points lie on a line through the anchor exactly when their direction vectors from it are parallel, and the gcd-reduced sign-normalised vector is a canonical representative of a direction. Since every line with two or more points contains an anchor that is examined, no line is missed.

Complexity

• Time — O(n² log V)
• Space — O(n)

Pitfalls

• Using dy / dx as a double breaks on vertical lines and can equate slopes that differ in the last bits.
• Without sign normalisation, points on opposite sides of the anchor land in different buckets and the count halves.
• gcd(0, 0) never arises because the points are distinct, but guarding g == 0 costs nothing.
• One or two points trivially lie on a line — return n directly.

Reference solution

Python

from math import gcd
from typing import List

def maxPoints(points: List[List[int]]) -> int:
    n = len(points)
    if n <= 2:
        return n
    best = 1
    for i in range(n):
        slopes = {}
        for j in range(n):
            if i == j:
                continue
            dx = points[j][0] - points[i][0]
            dy = points[j][1] - points[i][1]
            g = gcd(abs(dx), abs(dy)) or 1
            dx //= g
            dy //= g
            if dx < 0 or (dx == 0 and dy < 0):
                dx, dy = -dx, -dy
            key = (dx, dy)
            slopes[key] = slopes.get(key, 0) + 1
            best = max(best, slopes[key] + 1)
    return best

JavaScript

var maxPoints = function(points) {
    var n = points.length;
    if (n <= 2) return n;
    var gcd = function(a, b) {
        while (b !== 0) {
            var t = a % b;
            a = b;
            b = t;
        }
        return a;
    };
    var best = 1;
    for (var i = 0; i < n; i++) {
        var slopes = {};
        for (var j = 0; j < n; j++) {
            if (i === j) continue;
            var dx = points[j][0] - points[i][0];
            var dy = points[j][1] - points[i][1];
            var g = gcd(Math.abs(dx), Math.abs(dy));
            if (g === 0) g = 1;
            dx = dx / g;
            dy = dy / g;
            if (dx < 0 || (dx === 0 && dy < 0)) { dx = -dx; dy = -dy; }
            var key = dx + "/" + dy;
            slopes[key] = (slopes[key] === undefined ? 0 : slopes[key]) + 1;
            if (slopes[key] + 1 > best) best = slopes[key] + 1;
        }
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More math problems

• Minimum Cost to Split an Array Hard
• Count Anagrams Hard
• Smallest Range Covering Elements from K Lists Hard
• Minimum Number of Operations to Make Array Continuous Hard
• Bus Routes Hard
• Jump Game IV Hard