Max Points on a Line

Max Points on a Line is the classic hard geometry question. The algorithm is a hash map — the same "group by a key" idea as Group Anagrams. The difficulty is the key: a slope stored as a float breaks in ways that are hard to see, and the fix is a small piece of number theory. It is a good test of whether you think about exactness.

The problem

You get a list of points on a plane, each with integer coordinates [x, y]. Return the largest number of these points that lie on one straight line.

Example 1. [[1, 1], [2, 2], [3, 3]] → 3. All three are on the line y = x.

Example 2. [[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]] → 4. The points (4, 1), (3, 2), (2, 3) and (1, 4) lie on the line x + y = 5.

Constraints. 1 ≤ number of points ≤ 300, coordinates between −10⁴ and 10⁴, and all points are distinct.

Clarifying questions

• Can two points be identical? No, all distinct. (Duplicates are a follow-up.)
• Integer coordinates? Yes — which makes exact arithmetic possible.
• What if there are one or two points? The answer is 1 or 2: any two points share a line.
• Vertical lines? Yes, possible, and a classic source of bugs.

Approach 1: the simple way

Every line through two or more points is fixed by some pair of those points. So try every pair, and for each pair count how many points lie on the line through it. Test collinearity with the cross product from the core lesson — exact, and no division.

1def cross(o: list[int], a: list[int], b: list[int]) -> int:2    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])345def max_points_brute(points: list[list[int]]) -> int:6    """Try every pair; count points collinear with it. O(n^3)."""7    n = len(points)8    if n <= 2:9        return n10    best = 211    for i in range(n):12        for j in range(i + 1, n):13            count = 214            for k in range(n):15                if k != i and k != j and cross(points[i], points[j], points[k]) == 0:16                    count += 117            best = max(best, count)18    return best

O(n³) time, O(1) space. For 300 points that is about 13 million cross products; measured in Python, it took 2.0 seconds. It is correct, but too slow for most judges, and the same line is counted again for every pair on it.

The key insight

Fix one point, the anchor. Every other point defines a line through the anchor, and two points lie on the same line through the anchor exactly when they have the same slope from it. So group the other points by slope with a hash map. The biggest group, plus the anchor, is the best line through that anchor. Do this for each anchor: O(n²) pairs.

The whole problem is now: what is the hash key for a slope?

A float dy / dx fails in two ways. Vertical lines divide by zero. And floats round: two different slopes can round to the same float. With the points (0, 0), (94911151, 94911150) and (94911152, 94911151), the two slopes from (0, 0) are 94911150/94911151 and 94911151/94911152. They differ, but both round to the same float, so a float-keyed version returned 3 when the true answer is 2.

The exact key is the fraction itself, in lowest terms: (dx / g, dy / g) where g = gcd(dx, dy). Then (2, 1) and (4, 2) both become (2, 1). One more rule: the same line can give (1, −1) or (−1, 1), depending on which side of the anchor the point is. Normalise the sign — make dx positive, and if dx is 0, make dy positive — so both become (1, −1).

Approach 2: slopes as reduced fractions

1from collections import defaultdict2from math import gcd345def max_points(points: list[list[int]]) -> int:6    """For each anchor, group later points by exact reduced slope. O(n^2 log C)."""7    n = len(points)8    if n <= 2:9        return n10    best = 011    for i in range(n):12        x1, y1 = points[i]13        slopes: dict[tuple[int, int], int] = defaultdict(int)14        for j in range(i + 1, n):15            x2, y2 = points[j]16            dx, dy = x2 - x1, y2 - y117            g = gcd(dx, dy)                   # never 0: points are distinct18            dx, dy = dx // g, dy // g19            if dx < 0 or (dx == 0 and dy < 0):20                dx, dy = -dx, -dy             # one key per direction21            slopes[(dx, dy)] += 122            best = max(best, slopes[(dx, dy)])23    return best + 1                           # add the anchor itself

Step by step:

1. For each anchor i, start an empty map from slope to count.
2. For each later point j, compute the difference, reduce it by the GCD, and normalise the sign.
3. Count the key and track the best count seen.
4. Return best + 1 for the anchor.

Only later points are compared (j > i). Any line's points are all counted when its first point is the anchor, so looking back would only repeat work.

Dry run on Example 2. Anchor (1, 1) first:

Best so far is 2: the line through (1, 1), (3, 2), (5, 3), which is 3 points. Next anchor (3, 2):

Best is now 3, so the answer is 3 + 1 = 4. The sign rule was essential: without it, (4, 1) and (2, 3) would get different keys, (1, −1) and (−1, 1), and the answer would come out as 3. The remaining anchors do not beat 3.

Complexity. O(n² log C) time, where C is the coordinate range (here 2 × 10⁴): there are n(n − 1)/2 pairs, and each GCD takes O(log C) steps. The old version of this course wrote O(n² log n); the log comes from the size of the coordinates, not the number of points. O(n) space for one anchor's map. Measured on 300 random points: 0.02 seconds, against 2.0 seconds for the brute force. Both versions matched on 300 random point sets.

Edge cases

• One or two points. Returned directly: 1 or 2.
• Vertical lines. dx = 0, so the key is (0, 1) after normalising — a normal key, no division. [[0, 0], [0, 1], [0, -1], [1, 5]] returns 3.
• Horizontal lines. dy = 0; gcd(dx, 0) = |dx|, so the key is (1, 0).
• Negative coordinates. The differences can be negative; math.gcd returns a non-negative value, and the sign rule makes the key consistent.

Follow-ups

• "Points may repeat." Duplicates of the anchor lie on every line through it. Count them separately (dx = dy = 0 means a duplicate) and add that count to the anchor's best group, instead of hashing the key (0, 0).
• "Do three given points lie on one line?" One cross product: cross(p1, p2, p3) == 0. O(1), exact.
• "Find the convex hull of the points." Sort the points, then build the hull keeping only left turns — the sign of the same cross product (Andrew's monotone chain), O(n log n).