noodleProblems/
Max Points on a Line
#166

Max Points on a Line

AlgorithmhardMathHash TableArray

Given an array points where points[i] = [x, y] is a point on the plane, return the maximum number of points that lie on the same straight line.

No two points in the input are the same. A single point, or a pair of points, always counts as lying on a line.

Example cases

  • diagonal
    in points =
    11
    22
    33
    out 3
    All three points sit on the line y = x.
  • line plus stragglers
    in points =
    11
    32
    53
    41
    23
    14
    out 4
    (3,2), (4,1), (2,3), and (1,4) all satisfy x + y = 5; the other two points aren't on that line.
  • single point
    in points =
    00
    out 1
    One point trivially counts as lying on a line.
  • two points
    in points =
    00
    55
    out 2
    Any two distinct points always lie on some line together.

Constraints

  • 1 <= points.length <= 300
  • points[i].length == 2
  • -10^4 <= points[i][0], points[i][1] <= 10^4
  • All points in the input are unique.
Saved
points =
[[1,1],[2,2],[3,3]]