#149 Max Points on a Line

frequently reported atLinkedIn Apple Google Amazon Microsoft

the problem

In plain words

You get up to 300 distinct points with integer coordinates. Return the largest number of them that lie on one straight line.

in points = [[1,1],[2,2],[3,3]]

out 3

in points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]

out 4

(1,4), (2,3), (3,2) and (4,1) lie on x + y = 5.

1 ≤ points.length ≤ 300
−10⁴ ≤ xᵢ, yᵢ ≤ 10⁴
All points are distinct

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternGCD & prime sieve Group by a canonical key

Fix an anchor point. Every other point gives a direction (dx, dy) from it; points on the same line through the anchor share that direction once you divide by gcd(|dx|, |dy|) and fix the sign. Count directions in a HashMap — exact integers, no floating point.

solutions

From brute force to optimal

For each pair (i, j), count the later points k with a zero cross product.

For each pair i < j: dx, dy from i to j.
For each k > j: on the line if dx·(yₖ − yᵢ) == dy·(xₖ − xᵢ).
Track the best count.

timeO(n³)

About n³/6 triples: 4.5 million for n = 300.

spaceO(1)

Counters only; long products avoid overflow.

javajava.util.*

1class Solution {2    public int maxPoints(int[][] points) {3        int n = points.length;4        if (n <= 2) return n;5        int best = 2;6        for (int i = 0; i < n; i++) {7            for (int j = i + 1; j < n; j++) {                // the line through points i and j8                long dx = points[j][0] - points[i][0], dy = points[j][1] - points[i][1];9                int count = 2;10                for (int k = j + 1; k < n; k++) {11                    long ex = points[k][0] - points[i][0], ey = points[k][1] - points[i][1];12                    if (dx * ey == dy * ex) count++;         // cross product 0: k is on the same line13                }14                best = Math.max(best, count);15            }16        }17        return best;18    }19}

For each anchor, group the later points by their gcd-reduced, sign-normalised direction.

For each anchor i, a fresh HashMap<String, Integer>.
For each j > i: g = gcd(|dx|, |dy|); dx /= g; dy /= g; if dx < 0 (or dx == 0 and dy < 0), flip both signs.
count = map.merge(dx + "/" + dy, 1, Integer::sum); best = max(best, count + 1).

timeO(n² log C)

n²/2 pairs, each with a gcd on numbers up to C = 2·10⁴ (about 15 steps) and an O(1) average map update.

spaceO(n)

One map per anchor, at most n − 1 keys.

javajava.util.*

1class Solution {2    public int maxPoints(int[][] points) {3        int n = points.length, best = 1;4        for (int i = 0; i < n; i++) {5            Map<String, Integer> lines = new HashMap<>();   // reduced direction from point i → count6            for (int j = i + 1; j < n; j++) {7                int dx = points[j][0] - points[i][0];8                int dy = points[j][1] - points[i][1];9                int g = gcd(Math.abs(dx), Math.abs(dy));    // points are distinct, so g > 010                dx /= g;11                dy /= g;12                if (dx < 0 || (dx == 0 && dy < 0)) {        // one sign rule: (-2, -4) and (2, 4) are the same line13                    dx = -dx;14                    dy = -dy;15                }16                int onLine = lines.merge(dx + "/" + dy, 1, Integer::sum);17                best = Math.max(best, onLine + 1);          // + 1 for point i itself18            }19        }20        return best;21    }22 23    private static int gcd(int a, int b) {24        return b == 0 ? a : gcd(b, a % b);25    }26}

in the room

How to say it in the interview

talk track

Say up front: "I won't use double slopes — 0.0 vs −0.0 and vertical lines break them. I'll use a gcd-reduced (dx, dy) pair."
Explain why only j > i is enough: any line with k points is found from its first point as the anchor.
A record Slope(int dx, int dy) or a packed long also works as the key; a String is just the simplest to explain.

traps

double slope = (double) dy / dx as a key: -0.0 and 0.0 differ, and dx = 0 gives ±Infinity (or a crash with ints).
Forgetting to normalise the sign: (2, 4) and (−2, −4) must map to the same key.

what they ask next

Follow-ups

What if points could repeat?

Count duplicates of the anchor separately and add them to every line through it (and to the answer when all points are equal).

before you submit

Edge cases to test

One point → 1; two points → 2
Vertical (dx = 0) and horizontal (dy = 0) lines
Opposite directions (2, 4) and (−1, −2) are the same line
Nearly equal slopes like 10000/9999 and 9999/9998 are different lines

practise next