LeetCode #149 Hard

Max Points on a Line

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

arrayhash-tablegeometry

02

Intuition

Trying every pair as a line and rescanning all points costs O(n^3), and floating-point slopes can merge or split lines incorrectly. Fixing one point changes the question into counting how many other points share each direction from that anchor. A direction can be represented exactly by a reduced integer pair (dy, dx). Normalizing signs makes geometrically identical slopes use the same hash key.

How to spot this pattern

When points must be grouped by collinearity, anchor one point and group the rest by slope. Exact integer normalization is the reliable substitute for floating-point division in geometry hashing.

03

Approach

1

Choose each point as the line's anchor

For anchor i, inspect every later point j. Every line through the anchor is identified by the direction from points[i] to points[j], so the largest direction count plus the anchor gives the best line through i.

2

Reduce direction vectors with a greatest common divisor

Compute dx and dy, divide both by gcd(abs(dx), abs(dy)), and force dx nonnegative. Give vertical directions one canonical pair and horizontal directions another so equivalent slopes cannot receive different keys.

3

Count canonical slopes per anchor

Store each reduced pair in a fresh frequency map for the current anchor. Update the global answer with count + 1, where one accounts for the anchor itself. Rebuilding the map is essential because slopes from different anchors describe different lines.

04

Solution

▶1class Solution:
▶2    def maxPoints(self, points: List[List[int]]) -> int:
▶3        n = len(points)
▶4        answer = 1
▶5 
▶6        for i in range(n):
▶7            counts = defaultdict(int)
▶8            for j in range(i + 1, n):
▶9                dx = points[j][0] - points[i][0]
▶10                dy = points[j][1] - points[i][1]
▶11                if dx == 0:
▶12                    key = (1, 0)
▶13                elif dy == 0:
▶14                    key = (0, 1)
▶15                else:
▶16                    g = gcd(abs(dx), abs(dy))
▶17                    dx //= g
▶18                    dy //= g
▶19                    if dx < 0:
▶20                        dx = -dx
▶21                        dy = -dy
▶22                    key = (dy, dx)
▶23                counts[key] += 1
▶24                answer = max(answer, counts[key] + 1)
▶25 
▶26        return answer

05

Common pitfalls

Hashing floating-point slopes

✗ Wrong

slope = dy / dx

✓ Right

slope = (dy // g, dx // g)

Floating-point rounding can assign different keys to the same rational slope.

Leaving equivalent signs unnormalized

✗ Wrong

key = (dy // g, dx // g)

✓ Right

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

Vectors (1, 1) and (-1, -1) describe the same direction class.

Forgetting the anchor

✗ Wrong

answer = max(answer, counts[key])

✓ Right

answer = max(answer, counts[key] + 1)

The frequency counts other points, while the fixed anchor also lies on the line.

06

Edge cases

Only one point

Initialize the answer to one and return it without needing a pair.

A vertical line

All vectors with dx == 0 are normalized to (1, 0).

The same slope appears with opposite raw signs

Sign normalization moves the negative sign to dy, producing one shared key.

07

Complexity

Time

O(n^2 log C)

Space

O(n)

Each anchor hashes O(n) reduced directions; C bounds coordinate differences.