# LeetCode 149: Max Points on a Line

## Problem Restatement

We are given a list of 2D points:

```python
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](https://leetcode.com/problems/max-points-on-a-line/?utm_source=chatgpt.com))

## Examples

Example 1:

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

All three points lie on:

```text
y = x
```

Output:

```python
3
```

Example 2:

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

One maximum line contains:

```text
(1,1), (3,2), (5,3)
```

Output:

```python
3
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | `points: list[list[int]]` |
| Output | Maximum number of collinear points |
| Constraint | `1 <= len(points) <= 300` |
| Coordinates | Integers |

Function shape:

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

## Key Observation

Two points determine a unique line.

So for each point:

```python
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:

```python
(x1, y1)
```

For every other point:

```python
(x2, y2)
```

compute:

```python
dy = y2 - y1
dx = x2 - x1
```

The slope is:

```python
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:

```python
dy = 1
dx = 3
```

The slope is:

```python
0.333333...
```

Floating point precision can introduce rounding issues.

Instead, represent slopes as reduced integer pairs:

```python
(dy, dx)
```

normalized by greatest common divisor.

Example:

```python
(2, 4)
```

becomes:

```python
(1, 2)
```

Now equal slopes have identical representations.

## Normalizing Slopes

Suppose:

```python
dy = 6
dx = 9
```

Compute:

```python
gcd(6, 9) = 3
```

Normalize:

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

Now every equivalent slope maps to the same pair.

## Handling Signs

These are the same slope:

```python
(1, 2)
(-1, -2)
```

We must normalize signs consistently.

A common rule:

```python
dx > 0
```

If `dx < 0`, multiply both by `-1`.

For vertical lines:

```python
dx = 0
```

normalize to:

```python
(1, 0)
```

For horizontal lines:

```python
dy = 0
```

normalize to:

```python
(0, 1)
```

## Example Walkthrough

Consider:

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

Anchor:

```python
(1,1)
```

Other points:

| Point | `(dy, dx)` | Reduced |
|---|---|---|
| `(2,2)` | `(1,1)` | `(1,1)` |
| `(3,3)` | `(2,2)` | `(1,1)` |
| `(4,5)` | `(4,3)` | `(4,3)` |

Slope counts:

| Slope | Count |
|---|---:|
| `(1,1)` | `2` |
| `(4,3)` | `1` |

Largest count:

```python
2
```

Add the anchor point:

```python
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:

| Symbol | Meaning |
|---|---|
| `n` | Number of points |

For each point, we compare against all later points.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n^2)` | Pairwise comparisons |
| Space | `O(n)` | Slope hash map |

This is efficient enough for:

```python
n <= 300
```

## Implementation

```python
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:

```python
if n <= 2:
    return n
```

all points trivially lie on one line.

For each anchor point:

```python
for i in range(n):
```

create a slope counter:

```python
slopes = defaultdict(int)
```

Compute slope differences:

```python
dy = y2 - y1
dx = x2 - x1
```

Handle vertical lines:

```python
if dx == 0:
    dy = 1
    dx = 0
```

Handle horizontal lines:

```python
elif dy == 0:
    dy = 0
    dx = 1
```

Otherwise normalize:

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

Then reduce:

```python
dy //= g
dx //= g
```

Count occurrences:

```python
slopes[(dy, dx)] += 1
```

The line count through this anchor is:

```python
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:

```python
(i, j)
```

represents the same geometric relation as:

```python
(j, i)
```

So we only process each pair once.

## Testing

```python
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:

| Test | Why |
|---|---|
| Diagonal line | Standard slope case |
| Mixed points | Multiple candidate lines |
| Single point | Smallest input |
| Vertical line | `dx = 0` normalization |
| Horizontal line | `dy = 0` normalization |
| Negative coordinates | Sign normalization correctness |