Show problems as
Classic problem #149HardArrayHash TableMathGeometryEuclidean AlgorithmGreatest Common Divisor

Max Points on a Line

Real-world version: Most Pins on One Straight Line
Tracked in this browser only
Read Max Points on a Line on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Pin positions are given as points, each [x, y], and all of them are different.

Return the greatest number of pins that lie on a single straight line.

Examples

Example 1

Input
points = [[2, 7], [4, 11], [6, 15], [9, 2], [12, 2]]
Output
3

The pins at 2 and 7, 4 and 11, and 6 and 15 all lie on one line, climbing two across and four up each step, so three pins share it and no line holds more.

Example 2

Input
points = [[0, 0], [0, 1], [0, 2], [0, 3]]
Output
4

All four pins sit in one column, which is a straight line.

Example 3

Input
points = [[0, 0]]
Output
1

A single pin lies on a line of its own.

Constraints

  • 1 <= points.length <= 300
  • points[i].length == 2
  • -10000 <= points[i][0] <= 10000
  • -10000 <= points[i][1] <= 10000
  • All the pin positions are different

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def max_points(points: list[list[int]]) -> int:
Java
public int maxPoints(int[][] points)

More on the same topics