Max Points on a Line

HardMath · Geometry · Hash Map🧩 Math & Geometry LeetCode #149 ↗Updated Oct 30, 2026

Problem

You are given points[i] = [x, y], a set of distinct points with integer coordinates in the plane. Return the largest number of these points that lie together on one straight line.

Input[[1,1],[2,2],[3,3]]Output3

Input[[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]Output4

1 ≤ n ≤ 300 · -10⁴ ≤ x, y ≤ 10⁴ · all points are unique

Try it yourself

Java

class Solution {
    public int maxPoints(int[][] points) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Fix an anchor point: every other point on a common line through it shares the same direction. Represent the direction exactly as a reduced fraction (dy, dx) (divide by gcd, normalise the sign) and count equal keys in a hash map — no floating-point slopes.

PatternMath & Geometry

Instinct Digits, factors, slopes or distances hide a formula - find the invariant, then guard against overflow, negatives and floating-point error.

Memory hack Mod peels, gcd reduces, squares compare - and long saves the day. Peel digits with %10, reduce slopes with gcd, compare squared distances.

Open the Math & Geometry guide →

Approaches

Brute ForceEvery Pair Defines a Line + Cross Product

Time O(n³)Space O(1)

Any line with ≥ 2 points is fixed by some pair (i, j). For each pair, count the points k that are collinear, using the integer cross product (x_j-x_i)(y_k-y_i) == (y_j-y_i)(x_k-x_i). No division, so no precision issues; products stay below 4·10⁸, safe in int.

Java

public int maxPoints(int[][] points) {
    int n = points.length;
    if (n <= 2) return n;
    int best = 2;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++) {
            int dx = points[j][0] - points[i][0], dy = points[j][1] - points[i][1];
            int count = 2;
            for (int k = j + 1; k < n; k++) {
                int ex = points[k][0] - points[i][0], ey = points[k][1] - points[i][1];
                if (dx * ey == dy * ex) count++;
            }
            best = Math.max(best, count);
        }
    return best;
}

Exact and simple, but ~4.5·10⁶ pairs × 300 checks is slow.

OptimalAnchor + Hash Map of Reduced Slopes

Time O(n² log C)Space O(n)

For each anchor i, look only at later points j > i (a line is counted when its first point is the anchor). Reduce (dy, dx) by their gcd and force dx > 0 (or dx = 0, dy = 1 for vertical lines), so equal directions get the same key. Pack the pair into one long and count; the best line through i has maxCount + 1 points. (C = coordinate range, for the gcd.)

Java

public int maxPoints(int[][] points) {
    int n = points.length, best = 1;
    for (int i = 0; i < n; i++) {
        Map<Long, Integer> count = new HashMap<>();
        int localMax = 0;
        for (int j = i + 1; j < n; j++) {
            int dx = points[j][0] - points[i][0], dy = points[j][1] - points[i][1];
            int g = gcd(Math.abs(dx), Math.abs(dy)); // > 0: points are distinct
            dx /= g;
            dy /= g;
            if (dx < 0 || (dx == 0 && dy < 0)) { dx = -dx; dy = -dy; } // one sign
            long key = ((long) dy << 32) | (dx & 0xffffffffL);
            localMax = Math.max(localMax, count.merge(key, 1, Integer::sum));
        }
        best = Math.max(best, localMax + 1);
    }
    return best;
}
private int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

Quadratic with exact integer keys — the standard accepted solution.

Pro tip

If duplicates were allowed, count points equal to the anchor separately and add them to every line through it.

At a glance

Level	Approach	Time	Space
Brute Force	Every Pair Defines a Line + Cross Product	`O(n³)`	`O(1)`
Optimal	Anchor + Hash Map of Reduced Slopes	`O(n² log C)`	`O(n)`

Common pitfalls

Using double slopes — precision errors, and 0.0 vs -0.0 keys differ.
Not normalising the sign: (1,-2) and (-1,2) are the same direction.
Forgetting vertical lines (dx = 0) or returning 0 for a single point.

Interview tips

Ask whether points can repeat — it changes the counting.
Justify the exact key: reduced fraction with a canonical sign is unique per direction.
Mention cross-product collinearity as the division-free alternative.

Pattern

Anchor + hash of canonical keys → group items relative to a pivot (slopes, differences) using exact, normalised keys.

My notes saved in this browser