Max Points on a Line: Slope Counting with GCD

Given an array of points where points[i] = [xi, yi], return the maximum number of points that lie on the same straight line. That is LeetCode 149: Max Points on a Line.

Example: points = [[1,1],[2,2],[3,3]] returns 3 because all three points are collinear. A harder example: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]] returns 4. Can you spot which four?

Why this problem matters

Max Points on a Line is a clean test of two ideas: representing slopes in a way that avoids floating-point errors, and systematically counting matches using a hash map. The brute-force approach of checking every possible line through every pair is O(n^3). The key insight that reduces it to O(n^2) is anchoring on each point and grouping the others by slope.

The tricky part is not the algorithm itself. It is getting the slope representation right. Two slopes that look different as floats (like 2/4 and 1/2) must hash to the same key. GCD normalization solves this.

The approach

For each point (the "anchor"), compute the slope from the anchor to every other point. Store these slopes in a hash map and count how many points share the same slope. The largest count for any anchor, plus one for the anchor itself, is the answer.

The critical detail is how you represent the slope. Using floating-point division (dy / dx) fails because of precision errors. Instead, store the slope as a pair (dy, dx) reduced by their greatest common divisor. This ensures that (2, 4) and (1, 2) both normalize to (1, 2). To handle sign ambiguity, enforce a convention: if dx is negative, negate both dy and dx. If dx is zero (vertical line), set the key to (1, 0).

The algorithm:

1. For each anchor point i, create an empty hash map of slope keys to counts.
2. For each other point j, compute dy = yj - yi and dx = xj - xi.
3. Compute g = gcd(abs(dy), abs(dx)). Divide both by g.
4. Normalize the sign so dx is non-negative. If dx is 0, make dy positive.
5. Use the tuple (dy, dx) as the hash map key. Increment its count.
6. After processing all other points, the best count plus one (for the anchor) is the candidate answer for this anchor.
7. Track the global maximum across all anchors.

The solution

from math import gcd

def max_points(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(i + 1, n):
            dy = points[j][1] - points[i][1]
            dx = points[j][0] - points[i][0]
            if dx == 0:
                key = (1, 0)
            elif dy == 0:
                key = (0, 1)
            else:
                g = gcd(abs(dy), abs(dx))
                dy, dx = dy // g, dx // g
                if dx < 0:
                    dy, dx = -dy, -dx
                key = (dy, dx)
            slopes[key] = slopes.get(key, 0) + 1
        if slopes:
            best = max(best, max(slopes.values()) + 1)
    return best

Visual walkthrough

Let's trace through points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]. For each anchor, you build a slope map and find the largest group of collinear points.

At anchor (3,2), three other points share the normalized slope (-1,1): (4,1), (2,3), and (1,4). That gives 3 + 1 = 4 collinear points. No other anchor produces a larger group, so the answer is 4.

Walkthrough of the code

Early exit: If there are two or fewer points, they are always collinear. Return n directly.

Outer loop: Fix each point as the anchor. You only need to pair anchor i with points j > i because the line through i and j is the same as the line through j and i. An earlier anchor already counted lines involving earlier points.

Slope computation: For each pair, compute the raw dy and dx. Handle the special cases of vertical lines (dx == 0) and horizontal lines (dy == 0) first. For the general case, divide both by their GCD and normalize the sign so dx is positive. This guarantees that slopes like (2, -4) and (-1, 2) both become (-1, 2).

Counting: The hash map key is the normalized (dy, dx) tuple. Each key's value is the number of other points sharing that slope with the anchor. The maximum value plus one (for the anchor) gives the collinear count.

Global max: After all anchors, return the best count seen.

Complexity analysis

Time: The outer loop runs n times. The inner loop runs up to n - 1 times per anchor. GCD computation is O(log(max coordinate)) per pair, which is effectively constant for typical inputs. Total: O(n^2).

Space: The slope hash map holds at most n - 1 entries per anchor and is rebuilt each iteration. The input array is not modified. Total: O(n).

The building blocks

This problem is built on two reusable pieces that CodeBricks drills independently:

Slope representation with GCD

Representing the slope between two points as a GCD-normalized (dy, dx) pair avoids floating-point issues and ensures equivalent slopes hash to the same key:

g = gcd(abs(dy), abs(dx))
dy, dx = dy // g, dx // g
if dx < 0:
    dy, dx = -dy, -dx

This pattern appears whenever you need to compare ratios exactly: simplifying fractions, checking proportionality, or grouping items by ratio. The sign normalization step is easy to forget but essential. Without it, the slope from A to B and the slope from B to A produce different keys even though they represent the same line.

Per-anchor counting with a hash map

The pattern of fixing one element and using a hash map to group or count relationships with all other elements:

for i in range(n):
    counts = {}
    for j in range(i + 1, n):
        key = compute_key(i, j)
        counts[key] = counts.get(key, 0) + 1
    best = max(best, max(counts.values()) + 1)

You will see this structure in problems like Two Sum (fix one element, look up the complement), 3Sum (fix one element, run two-pointer on the rest), and any problem that asks "for each element, how many others share property X?" The hash map turns an O(n) scan per pair into an O(1) lookup, collapsing what would be O(n^3) brute force into O(n^2).

Edge cases

• Duplicate points: If multiple points share the same coordinates, every slope from the anchor to those duplicates produces dy = 0, dx = 0. You need to count duplicates separately (or let the gcd(0, 0) case be handled). The solution above handles this implicitly because j > i avoids self-pairs, and two identical points produce dx = 0, dy = 0, which the dx == 0 branch maps to (1, 0). This groups all duplicates with vertical-line points. A more careful approach counts duplicates explicitly and adds them to every slope group.
• Vertical lines: All points with the same x-coordinate lie on a vertical line. The slope is undefined in dy/dx form, but the (1, 0) key handles this cleanly.
• Two points: Any two points define a line. Return 2 immediately.
• All collinear: If every point lies on the same line, the first anchor's slope map has a single entry with count n - 1, and the answer is n.

From understanding to recall

You have seen how GCD normalization and per-anchor counting combine to solve this problem. The algorithm is only a dozen lines, but the details matter: the sign convention, the special cases for vertical and horizontal lines, the +1 for the anchor. Under pressure, any of these can slip.

Spaced repetition locks it in. You practice writing the GCD normalization, the nested-loop structure with the slope map, and the edge-case handling from scratch. Do it today, again in two days, again in five. After a few reps, you see "max points on a line" and the slope-counting pattern writes itself.

GCD-based slope representation and per-anchor hash map counting are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• 3Sum: Sorting Plus Two Pointers - Another O(n^2) problem that fixes one element and efficiently processes the rest
• Valid Sudoku: Hash Set Validation - Uses hash maps for structured duplicate detection across multiple groups simultaneously

CodeBricks breaks Max Points on a Line into its GCD slope normalization and per-anchor counting building blocks, then drills them independently with spaced repetition. You type the normalized slope computation, the hash map grouping loop, and the edge-case guards from scratch until the pattern is automatic. When a geometry or ratio-counting problem shows up in your interview, you do not think about it. You just write it.