LeetCode 149: Max Points on a Line

Problem Restatement

We are given a list of 2D points:

points[i] = [xi, yi]

Return the maximum number of points that lie on the same straight line.

A line may be horizontal, vertical, diagonal, or any slope.

LeetCode constrains the number of points to at most 300, which allows an O(n^2) solution. (leetcode.com)

Examples

Example 1:

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

All three points lie on:

y = x

Output:

3

Example 2:

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

One maximum line contains:

(1,1), (3,2), (5,3)

Output:

3

Input and Output

Function shape:

class Solution:
    def maxPoints(self, points: list[list[int]]) -> int:
        ...

Key Observation

Two points determine a unique line.

So for each point:

points[i]

we can treat it as an anchor and count how many other points form the same slope relative to it.

If many points share the same slope from the anchor point, then they all lie on the same line.

Basic Idea

Fix one point:

(x1, y1)

For every other point:

(x2, y2)

compute:

dy = y2 - y1
dx = x2 - x1

The slope is:

dy / dx

Count how many times each slope appears.

The largest slope frequency plus the anchor point gives the largest line through that anchor.

Take the global maximum across all anchors.

Why Floating Point Is Dangerous

Suppose:

dy = 1
dx = 3

The slope is:

0.333333...

Floating point precision can introduce rounding issues.

Instead, represent slopes as reduced integer pairs:

(dy, dx)

normalized by greatest common divisor.

Example:

(2, 4)

becomes:

(1, 2)

Now equal slopes have identical representations.

Normalizing Slopes

Suppose:

dy = 6
dx = 9

Compute:

gcd(6, 9) = 3

Normalize:

(6 // 3, 9 // 3)
= (2, 3)

Now every equivalent slope maps to the same pair.

Handling Signs

These are the same slope:

(1, 2)
(-1, -2)

We must normalize signs consistently.

A common rule:

dx > 0

If dx < 0, multiply both by -1.

For vertical lines:

dx = 0

normalize to:

(1, 0)

For horizontal lines:

dy = 0

normalize to:

(0, 1)

Example Walkthrough

Consider:

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

Anchor:

(1,1)

Other points:

Slope counts:

Largest count:

2

Add the anchor point:

2 + 1 = 3

So the maximum line through (1,1) contains 3 points.

Algorithm

For each point i:

1. Create an empty slope counter.
2. Compare point i with every later point j.
3. Compute normalized slope (dy, dx).
4. Count how many times each slope occurs.
5. Track the largest slope frequency for this anchor.
6. Update the global maximum.

Correctness

Fix an anchor point p.

Any other point q forms exactly one line through p, determined by the slope between p and q.

All points collinear with p share the same slope relative to p. After normalization, all equivalent slopes map to the same (dy, dx) pair.

Therefore, counting equal normalized slopes counts exactly the number of points on the same line through p.

For each anchor point, the algorithm computes the maximum number of collinear points through that anchor.

Since every line contains at least one anchor point considered during the outer loop, the global maximum across all anchors equals the maximum number of collinear points in the entire set.

Thus, the algorithm returns the correct answer.

Complexity

Let:

For each point, we compare against all later points.

This is efficient enough for:

n <= 300

Implementation

from collections import defaultdict
from math import gcd

class Solution:
    def maxPoints(self, points: list[list[int]]) -> int:
        n = len(points)

        if n <= 2:
            return n

        answer = 1

        for i in range(n):
            slopes = defaultdict(int)

            x1, y1 = points[i]
            local_max = 0

            for j in range(i + 1, n):
                x2, y2 = points[j]

                dy = y2 - y1
                dx = x2 - x1

                if dx == 0:
                    dy = 1
                    dx = 0

                elif dy == 0:
                    dy = 0
                    dx = 1

                else:
                    if dx < 0:
                        dy = -dy
                        dx = -dx

                    g = gcd(abs(dy), abs(dx))

                    dy //= g
                    dx //= g

                slopes[(dy, dx)] += 1

                local_max = max(
                    local_max,
                    slopes[(dy, dx)],
                )

            answer = max(answer, local_max + 1)

        return answer

Code Explanation

If there are at most two points:

if n <= 2:
    return n

all points trivially lie on one line.

For each anchor point:

for i in range(n):

create a slope counter:

slopes = defaultdict(int)

Compute slope differences:

dy = y2 - y1
dx = x2 - x1

Handle vertical lines:

if dx == 0:
    dy = 1
    dx = 0

Handle horizontal lines:

elif dy == 0:
    dy = 0
    dx = 1

Otherwise normalize:

g = gcd(abs(dy), abs(dx))

Then reduce:

dy //= g
dx //= g

Count occurrences:

slopes[(dy, dx)] += 1

The line count through this anchor is:

local_max + 1

because the counter only counts the other points, not the anchor itself.

Why We Only Compare j > i

This avoids duplicate work.

The pair:

(i, j)

represents the same geometric relation as:

(j, i)

So we only process each pair once.

Testing

def run_tests():
    s = Solution()

    assert s.maxPoints([
        [1, 1],
        [2, 2],
        [3, 3],
    ]) == 3

    assert s.maxPoints([
        [1, 1],
        [3, 2],
        [5, 3],
        [4, 1],
        [2, 3],
        [1, 4],
    ]) == 3

    assert s.maxPoints([
        [1, 1],
    ]) == 1

    assert s.maxPoints([
        [1, 1],
        [1, 2],
        [1, 3],
    ]) == 3

    assert s.maxPoints([
        [1, 1],
        [2, 1],
        [3, 1],
        [4, 1],
    ]) == 4

    assert s.maxPoints([
        [0, 0],
        [1, 1],
        [-1, -1],
    ]) == 3

    print("all tests passed")

run_tests()

Test meaning: