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 trivially forms 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 biggest 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

class Solution:
    def maxPoints(self, 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 that’s ~2.7×10⁷ inner iterations times the pair loop — actually 300³ ≈ 2.7×10⁷… the pair loop makes it ~n³/2 ≈ 1.3×10⁷·300, i.e. borderline. It’s correct but redundantly re-derives each line from every pair on it.

Approach 2 — Anchor + slope hashing

The insight: collinear points through a fixed anchor all share the same slope relative to that anchor. So 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 is the answer — and each line of size k is rediscovered from each of its points, which is fine.

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, e.g., (1, 2) and (-1, -2) map to the same key.

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

class Solution:
    def maxPoints(self, 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).