Max Points on a Line

Given an array of points, return the maximum number of points that lie on the same straight line. A naive check of every line is too slow for large inputs.

Why this is worth learning

Anchor one point and group other points by an exact normalized direction. Rational slope keys avoid floating equality errors, and duplicate coordinates must be counted separately from direction.

Before coding: one-minute experiment

For points [0,0], [0,0], [1,1], [2,2], what is the answer and why is slope (0,0) not an ordinary direction?

Function signature

func MaxPoints(points [][]int) int

Inputs / outputs

• points: list of [x, y].
• Return: maximum number of collinear points.

Example

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

All three share slope 1.

Constraints

• 0 <= len(points) <= 300
• Coordinates fit in 32-bit signed int

Core idea (near-solution)

A complete small-instance model tries every line through a distinct point pair and counts all collinear points, costing O(n³). Fix one anchor to reuse work: all other points can be grouped by the line they define with that anchor. Exact reduced directions make proportional vectors share a key without floating equality. Coincident points have no direction, so count them separately and add them to every line through the anchor.

Fix an anchor point i. For every other point j, compute the slope from i to j and count how many share the same slope. Normalize slopes using gcd to avoid floating errors. Track duplicates.

Invariant: for a fixed anchor, all points on the same line map to the same reduced (dy, dx).

Algorithm (step-by-step)

1. If n <= 2, return n.
2. For each anchor i:
   • Initialize a map slope -> count.
   • Set dup = 0, localMax = 0.
3. For each j > i:
   • If points[j] == points[i], increment dup.
   • Else compute dx, dy; reduce by gcd; normalize sign (e.g., make dx > 0 or handle vertical).
   • Increment map for that slope and update localMax.
4. Best for anchor = localMax + dup + 1.
5. Return the global max.

Correctness sketch

For a fixed anchor, every nonduplicate point on one line has proportional (dx,dy). Normalize sign and divide by gcd so equivalent directions share one key, treating vertical and horizontal lines consistently. Distinct normalized directions correspond to distinct lines through the anchor. Duplicate coordinates lie on every such line, so add their count plus the anchor to the largest direction bucket. Considering each anchor reaches an anchor on every candidate maximum line; using only later points still counts the full line when its earliest-index point is the anchor. If all points coincide, the duplicate count plus one yields the correct total.

Trace (hand walkthrough)

Example input:
points = [[1,1],[2,2],[3,3]]
Output: 3

All three share slope 1.

Walk:
- anchor [1,1]: slopes to [2,2] and [3,3] both (1,1)
- count=3 on same line -> output 3

Pitfalls to avoid

• Floating point slope (precision errors).
• Forgetting duplicate points.
• Incorrect sign normalization (e.g., (1,-1) vs (-1,1)).
• Handling vertical/horizontal lines inconsistently.

Debugging lens

Test vertical/horizontal lines, opposite directions, duplicate points, and large coordinates. On the supported 64-bit target, differences of two signed-32-bit coordinates fit int; computing a cross product in the same signed width could still overflow.

Complexity

With fixed signed-32-bit coordinates on a 64-bit target, O(n²) word-operation time and O(n) auxiliary slope-map entries per anchor. With variable-width coordinates bounded by C, gcd/key construction introduces an O(log C) factor.

Implementation notes (Go)

• Use gcd on absolute values and then normalize sign consistently.
• Encode slope as a string or pair key (dy/dx) in a map.

Reconstruction checkpoint

For points [0,0], [0,0], [1,1], [2,2], what is the answer and why is slope (0,0) not an ordinary direction?

Return to Math · Module quiz