Max Points on a Line

Max Points on a Line looks like geometry but is really a hashing problem. The key realization: a straight line is pinned down by one anchor point and a direction (slope), so if you fix a point and bucket every other point by its slope, the biggest bucket is the longest line through that anchor.

The slow way first

You could test every triple of points and check whether they are collinear — that is O(n³). Even checking every pair of lines is wasteful. The slowness comes from re-deriving the same line over and over instead of grouping points that already agree on a direction.

The question to ask: if I stand on one point and look outward, how many other points are in exactly the same direction? Points in the same direction from me are on the same line through me. That is a counting problem — and counting by a key is what a hash map does best.

The idea: anchor, then bucket by slope

Fix one point as the anchor. For every other point, compute the slope from the anchor: dy = by - ay, dx = bx - ax. Store the slope as a key in a map and increment its count. Points sharing a slope key are collinear with the anchor, so the largest count (plus the anchor itself) is the longest line through it. Repeat with every point as the anchor and keep the global max.

The one trap is the slope key. Using the float dy / dx invites rounding error, and a single number cannot tell a vertical line apart. The safe key is the reduced pair (dy / g, dx / g) where g = gcd(dy, dx), so (1,1), (2,2), and (3,3) all collapse to the same key.

Walk through it

Step through the animation. We fix anchor A = (0,0) and fan out. B = (1,1) gives slope (1,1). C = (2,2) is 2/2, which reduces to (1,1) — the same line, so its bucket grows to 2. D and E land in their own buckets. The biggest bucket from A is (1,1) with 2 points, so the line A, B, C has 3 points. No later anchor beats it, so the answer is 3.

Pseudocode

best = 1
for each anchor point (ax, ay):
    make an empty map "slopes"
    for each later point (bx, by):
        dy, dx = by - ay, bx - ax
        g = gcd(dy, dx) (or 1 if both are 0)
        key = (dy / g, dx / g)         # reduced slope, exact integers
        slopes[key] += 1
        best = max(best, slopes[key] + 1)   # +1 counts the anchor
return best

The Python solution

def max_points(points):
    best = 1
    for i, (ax, ay) in enumerate(points):
        slopes = {}
        for bx, by in points[i + 1:]:
            dy, dx = by - ay, bx - ax
            g = gcd(dy, dx) or 1
            key = (dy // g, dx // g)
            slopes[key] = slopes.get(key, 0) + 1
            best = max(best, slopes[key] + 1)
    return best

• The outer loop fixes each (ax, ay) as the anchor; slopes is reset fresh for every anchor.
• We only look at points[i + 1:] — points after the anchor — because any earlier pair was already counted from the other point as anchor.
• dy, dx is the raw direction; dividing both by their gcd gives a canonical integer slope key, so (1,1), (2,2), (3,3) all match.
• Line 7 uses or 1 so a duplicate point (where dy and dx are both 0, making gcd 0) does not divide by zero.
• slopes[key] + 1 adds the anchor itself to the bucket, and best keeps the running maximum.

Complexity

For each of the n anchors we scan the remaining points once and hash a slope, giving O(n²) time. The map holds at most n slope keys for one anchor, so extra space is O(n).

When this pattern shows up

Practice