Max Points on a Line

Hard Arrays & Hashing Hashing Original on LeetCode

Max Points on a Line is a hard arrays & hashing problem solved with the hashing pattern. The best approach, optimal (slopes from each anchor in a hash map), runs in O(n² · log C) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (every pair, count the rest) up.

Problem

You are given an array points where points[i] = [x_i, y_i] is a point on the 2D plane. All points are distinct.

Return the largest number of points that lie on one straight line.

Examples

Example 1

Input
points = [[0,0],[2,2],[5,5],[1,3]]
Output
3
Why
(0,0), (2,2) and (5,5) all lie on the line y = x; (1,3) is off it.

Example 2

Input
points = [[1,1]]
Output
1
Why
A single point is on a line by itself.

Example 3

Input
points = [[0,0],[1,0],[2,1],[3,1],[4,2],[0,4]]
Output
3
Why
(0,0), (2,1) and (4,2) share the slope 1/2 through the origin. No line passes through four of the points.

Constraints

  • 1 <= points.length <= 300
  • points[i].length == 2
  • -10^4 <= x_i, y_i <= 10^4
  • All points are distinct.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (every pair, count the rest)O(n³)O(1)
Optimal (slopes from each anchor in a hash map)O(n² · log C)O(n)

1Brute force (every pair, count the rest)

TimeO(n³)n² / 2 pairs, each checked against all n points.
SpaceO(1)Only counters; the products fit easily in an int at these coordinate sizes.

For each pair of points, the line through them is fixed. Count how many points lie on it using the cross product, which is zero exactly when three points are collinear. Keep the best count.

  1. If there are at most 2 points, return their number.
  2. For each pair (i, j), count the points k with (x_j - x_i)(y_k - y_i) - (y_j - y_i)(x_k - x_i) == 0.
  3. Return the largest count.
class Solution {
    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 = 0;
                for (int k = 0; k < n; k++) {
                    int ex = points[k][0] - points[i][0], ey = points[k][1] - points[i][1];
                    if ((long) dx * ey - (long) dy * ex == 0) count++;
                }
                best = Math.max(best, count);
            }
        }
        return best;
    }
}

2Optimal (slopes from each anchor in a hash map)

TimeO(n² · log C)n² / 2 pairs, each needing a gcd on coordinates up to C = 2 · 10^4.
SpaceO(n)The map for one anchor holds at most n - 1 directions.

Every line through the anchor point i is identified by its direction. For each later point j, compute (dx, dy), divide both by their gcd, and flip signs so dx > 0, or dx == 0 and dy > 0. Points with the same reduced direction lie on the same line through i. The biggest group plus the anchor itself is the best line through i; the answer is the best over all anchors.

  1. If there are at most 2 points, return their number.
  2. For each anchor i, clear a map; for each j > i compute dx, dy, g = gcd(|dx|, |dy|), divide, normalise the sign.
  3. Increment map[(dx, dy)] and track the largest count for this anchor.
  4. best = max(best, largest + 1). Return best.
class Solution {
    public int maxPoints(int[][] points) {
        int n = points.length;
        if (n <= 2) return n;
        int best = 2;
        for (int i = 0; i < n; i++) {
            Map<Long, Integer> slopes = new HashMap<>();
            int local = 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));
                dx /= g;
                dy /= g;
                if (dx < 0 || (dx == 0 && dy < 0)) { dx = -dx; dy = -dy; }
                long key = (long) dx * 100000L + dy;
                local = Math.max(local, slopes.merge(key, 1, Integer::sum));
            }
            best = Math.max(best, local + 1);
        }
        return best;
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

Edge cases to test

  • One or two points (the answer equals the number of points)
  • A vertical line (equal x values, so the slope is undefined)
  • A horizontal line (slope 0)
  • Slopes that are equal as fractions but written with different numbers, like 2/4 and -1/-2
  • All points on one line

Hints

Hint 1

Two points fix a line. For a pair, how would you test whether a third point lies on the same line without dividing?

Hint 2

Fix one anchor point. Every other point on a common line through the anchor has the same direction from it, so group the other points by direction.

Hint 3

Represent a direction exactly as a reduced fraction (dy, dx): divide by the gcd and fix the sign, so equal slopes always get the same key and floating-point error never appears.

FAQ

What is the best time complexity for Max Points on a Line?

Optimal (slopes from each anchor in a hash map) runs in O(n² · log C) time and O(n) extra space. n² / 2 pairs, each needing a gcd on coordinates up to C = 2 · 10^4.

Which pattern does Max Points on a Line use?

It is a arrays & hashing problem that uses the hashing pattern. Other problems with the same pattern: Group Anagrams, First Unique Character in a String, Number of Matching Subsequences.

Is there a brute force solution for Max Points on a Line?

Yes. Brute force (every pair, count the rest) takes O(n³) time and O(1) space. For each pair of points, the line through them is fixed.

Which edge cases should I test for Max Points on a Line?

One or two points (the answer equals the number of points); A vertical line (equal x values, so the slope is undefined); A horizontal line (slope 0); Slopes that are equal as fractions but written with different numbers, like 2/4 and -1/-2; All points on one line.