Max Points on a Line

Problem

You are given points, a list of [x, y] coordinates on the 2-D plane. Return the maximum number of points that all lie on the same straight line.

Any two points define a line; the question is how many of the given points can share one line simultaneously.

Examples

• points = [[1,1],[2,2],[3,3]] → 3 — all three lie on the line y = x.
• points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]] → 4 — the four points [1,4],[2,3],[3,2],[4,1] all satisfy x + y = 5, so they share one line.
• points = [[0,0]] → 1 — a single point counts as a line of size 1.

Constraints

• 1 <= len(points) <= 300
• -10^4 <= x, y <= 10^4
• All points are distinct.
• With n <= 300, an O(n²) or O(n² log n) solution is comfortably fast; the challenge is comparing slopes exactly, without floating-point error.

Think about it first

TL;DR

For each anchor point, hash the reduced-fraction slope to every other point and take the largest bucket. O(n²) time, O(n) space.

Approach 1 — Brute force: test every triple

For every pair (i, j), count how many points lie on the line through them by testing all other points for collinearity with the cross-product test.

Collinearity of A, B, C holds when the signed area of the triangle is zero: (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x) == 0. Using cross products keeps everything in integers — no division, no float error.

from typing import List

def maxPoints(points: List[List[int]]) -> int:
    n = len(points)
    if n <= 2:
        return n

    best = 2
    for i in range(n):
        for j in range(i + 1, n):
            ax, ay = points[i]
            bx, by = points[j]
            count = 2
            for k in range(n):
                if k == i or k == j:
                    continue
                cx, cy = points[k]
                cross = (bx - ax) * (cy - ay) - (by - ay) * (cx - ax)
                if cross == 0:
                    count += 1
            best = max(best, count)
    return best

Complexity: O(n³) time, O(1) space. With n = 300 the triple loop runs about n³/2 ≈ 1.3×10⁷ iterations, which is fast enough. It is correct but wasteful: it re-derives each line from every pair of points that lie on it.

Approach 2 — Anchor + slope hashing

Collinear points through a fixed anchor all share the same slope relative to that anchor. Fix each point as an anchor, compute the slope to every other point, and count identical slopes with a hash map. The largest count for an anchor, plus the anchor itself, is the biggest line through it. Taking the max over all anchors gives the answer. Each line of size k is rediscovered from each of its points, which does not affect the result.

The one subtlety is representing slope exactly. Floating dy/dx loses precision, so we store the slope as a reduced integer pair (dy // g, dx // g) where g = gcd(dy, dx), normalized to a canonical sign so that, for example, (1, 2) and (-1, -2) map to the same key.

from typing import List
from collections import defaultdict
from math import gcd

def maxPoints(points: List[List[int]]) -> int:
    n = len(points)
    if n <= 2:
        return n

    best = 1
    for i in range(n):
        ax, ay = points[i]
        slopes = defaultdict(int)
        for j in range(n):
            if j == i:
                continue
            dx = points[j][0] - ax
            dy = points[j][1] - ay

            if dx == 0:                 # vertical line
                key = ("inf", 0)
            elif dy == 0:               # horizontal line
                key = (0, "inf")
            else:
                g = gcd(dx, dy)
                dx //= g
                dy //= g
                if dx < 0:              # canonical sign: keep dx > 0
                    dx, dy = -dx, -dy
                key = (dy, dx)

            slopes[key] += 1
            best = max(best, slopes[key] + 1)   # + 1 for the anchor
    return best

Walkthrough with points = [[1,1],[2,2],[3,3]]:

• Anchor (1,1):
  • to (2,2): dx=1, dy=1, gcd=1, key (1, 1) → count 1, best = 2.
  • to (3,3): dx=2, dy=2, gcd=2 → (1, 1) → count 2, best = 3.
• Anchors (2,2) and (3,3) also find slope (1,1) shared by the other two, confirming 3.
• Answer: 3.

Why the sign convention matters: from anchor (2,2), point (1,1) gives dx=-1, dy=-1, and point (3,3) gives dx=1, dy=1. Without normalizing to dx > 0 these hash to different keys (−1,−1) vs (1,1) and the line splits into two buckets. Forcing dx > 0 collapses them to one.

Complexity: O(n²) time (each anchor scans all points, gcd is effectively constant on bounded ints), O(n) space for the per-anchor map.

Common pitfalls

• Using floating-point slope dy/dx: 1/3 vs 2/6 can differ in the last bit, silently splitting a line. Always reduce to an integer (dy, dx) pair with gcd.
• Forgetting the sign convention, so opposite directions along the same line hash differently.
• Mishandling vertical (dx == 0) and horizontal (dy == 0) lines — give them their own sentinel keys so gcd(0, k) edge cases don’t collide.
• Returning the bucket size without +1 for the anchor, undercounting every line by one.
• Not special-casing n <= 2: with 0, 1, or 2 points the answer is just n.

Pattern takeaway

For collinearity, anchor-and-slope turns a geometric question into counting equal keys — but only if the key is exact. Reduce direction vectors by their gcd and pin a sign convention so equal lines share one canonical key. The broader lesson: when floats threaten precision, re-express the invariant with integer arithmetic (reduced fractions, or cross-product zero tests).