149. Max Points on a Line

Problem¶

Given up to 300 unique 2D points, return the largest number lying on one straight line.

Input: [[1,4], [2,3], [3,2], [4,1], [2,1]]
Line:  x + y = 5
Output: 4

Key trick¶

For each point as an anchor, count equal slopes to every other point, representing each slope exactly as a reduced integer pair using gcd.

Trap¶

• Comparing floating-point slopes can be fragile.
• Vertical lines cause division by zero.
• Equivalent directions such as (1, 2) and (-1, -2) must use the same normalized key.
• Checking every line against every point takes \(O(n^3)\) time.

Why is it interesting?¶

It turns a geometric collinearity problem into repeated hash-map counting while requiring exact rational normalization.

Python solution¶

import math


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

        best = 2

        for i in range(n):
            slopes = {}
            x1, y1 = points[i]

            for j in range(i + 1, n):
                x2, y2 = points[j]
                dx = x2 - x1
                dy = y2 - y1

                # Reduce the direction to its smallest integer pair.
                g = math.gcd(abs(dx), abs(dy))
                dx //= g
                dy //= g

                # Give opposite representations one canonical sign.
                if dx < 0 or (dx == 0 and dy < 0):
                    dx = -dx
                    dy = -dy

                slope = (dy, dx)
                slopes[slope] = slopes.get(slope, 0) + 1
                best = max(best, slopes[slope] + 1)

        return best

Time complexity: \(O(n^2)\).

Space complexity: \(O(n)\).

Comment on my solution¶

• Your solution works for the stated constraints and correctly handles vertical lines separately.
• Its triple loop takes \(O(n^3)\) time, while grouping slopes per anchor reduces this to \(O(n^2)\).
• Float slopes are less robust and require special handling; reduced integer pairs handle every direction uniformly.
• The example comment repeats [1,4]; the fourth point on that line should be [4,1].

# WORKS
class Solution:
    def maxPoints(self, points: list[list[int]]) -> int:
        # - [[1,1],[2,2],[3,3]] -> 3 (slope of line is 1)
        # - [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]] -> 4
        #   - [1,4], [2,3], [3,2], [4,1] slope of line -1

        # Ideas
        # - group by slope
        #   - compute slopes
        #     - then group by slope
        #   - or for each slope
        #     - count how many point are on the line
        #       - if count == len(points)
        #         - stop early
        #   - must be careful for vertical line (see this later)

        n = len(points)

        best = 1

        # non vertical lines
        for i in range(n):
            x, y = points[i]
            for j in range(i + 1, n):
                xx, yy = points[j]
                if x == xx:
                    continue
                slope = (y - yy) / (x - xx)
                count = 2
                for k in range(j + 1, n):
                    xxx, yyy = points[k]
                    if x == xxx:
                        continue
                    if (y - yyy) / (x - xxx) == slope:
                        count += 1
                best = max(best, count)
                if count == n:
                    return n

        # vertical line
        vertical_lines = {}
        for x,y in points:
            vertical_lines[x] = vertical_lines.get(x, 0) + 1
        best = max(best, max(vertical_lines.values()))
        return best

Extra¶

Storing the slope as a reduced pair of integers¶

Why this approximated slope using gcd charaterise lines uniquely? Give me more details and demonstrate the result mathematically.

The GCD representation is not an approximation. It stores the slope exactly as a reduced pair of integers.

For an anchor point \(P=(x_0,y_0)\) and another point \(Q=(x,y)\), define the direction vector

The usual slope is

Instead of performing the division, store

This is the slope written as a reduced fraction.

Example¶

Using \(P=(1,1)\) as the anchor:

Q = (3,2):  (dy, dx) = (1,2)  -> gcd = 1 -> (1,2)
R = (5,3):  (dy, dx) = (2,4)  -> gcd = 2 -> (1,2)
S = (-1,0): (dy, dx) = (-1,-2) -> gcd = 1 -> (-1,-2) -> (1,2)

All three directions normalize to (1, 2), representing the exact slope \(1/2\).

By contrast:

T = (2,3): (dy, dx) = (2,1) -> (2,1)

This represents slope \(2\), so \(T\) is not on the same line through \(P\).

Why the reduced pair is unique¶

Two direction vectors have the same slope exactly when

Without division, this is equivalent to

After dividing each pair by its GCD, both pairs are primitive: their components have no common factor. Two primitive integer pairs representing the same ratio can differ only by sign:

The sign-normalization rule converts both to the same pair:

if dx < 0 or (dx == 0 and dy < 0):
    dx = -dx
    dy = -dy

Therefore each possible slope has one canonical representation.

Vertical and horizontal lines¶

The representation also avoids division by zero:

• Vertical direction:

• Horizontal direction:

Thus all vertical lines share the slope key (1, 0), and all horizontal lines share (0, 1).

Important distinction¶

A slope alone does not identify a line globally because parallel lines have the same slope. It identifies a line uniquely only when combined with the fixed anchor point.

For example, both lines have slope \(1\):

During one hash-map pass, every compared point shares the same anchor. Therefore equal normalized slopes mean the points lie on the same line through that anchor. A new hash map is created for each new anchor.