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.

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)

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

• Invariant: for a fixed anchor, all points on the same line map to the same reduced (dy, dx).
• The formula/transform follows from number properties or monotonicity.
• Each iteration preserves the mathematical invariant.
• Thus the computed value matches the definition of the problem.

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.

Complexity

• Time: O(n^2).
• Extra space: O(n) per anchor.

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.