Stars on One Straight Line

Hard

A sky chart marks a set of stars: stars[i] = [x, y] gives the integer coordinates of the i-th star. All points are distinct. Return the largest number of stars that lie on a single straight line. The line can be any line: slanted, horizontal or vertical.

Example 1

stars=[[0, 0], [2, 1], [4, 2], [1, 3], [3, 0]] → 3

The stars (0, 0), (2, 1) and (4, 2) lie on one line. No four stars here share a line.

Example 2

stars=[[-1, 2], [-1, -4], [-1, 0], [3, 3]] → 3

Three stars sit on the vertical line x = -1.

Example 3

stars=[[5, 5]] → 1

Constraints

1 ≤ len(stars) ≤ 300
stars[i] = [x, y]
-10⁴ ≤ x, y ≤ 10⁴
No two stars share a point

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Geometry Array Hash Table Math

Similar problems

Smallest Paddock Medium Fewest Lines Through the Dots Medium Grid Points Under Circles Medium Does the Robot Cross Its Trail Hard Rope Around the Posts Hard

Input

stars=[[0, 0], [2, 1], [4, 2], [1, 3], [3, 0]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 100 tests on the server, hidden ones included.