Max Points on a Line
- Array
- Hash Map
- Math
- Greatest Common Divisor
Given an array points where points[i] is [x, y], return the maximum number of points that lie on one straight line.
All input points are distinct. Normalize each slope exactly rather than using floating-point division.
Three points on a rising line
- Input
"points": [ [0, 1], [2, 5], [4, 9], [3, 0], [5, 2] ]
- Output
3
Explanation: The points [0, 1], [2, 5], and [4, 9] share the line y = 2x + 1.
Four points on a falling line
- Input
"points": [ [-2, 4], [0, 2], [2, 0], [4, -2], [1, 5], [3, 3] ]
- Output
4
Explanation: The first four points lie on y = 2 - x.
Constraints
- 1 <= points.length <= 300
- points[i].length is 2
- -10,000 <= x, y <= 10,000
Follow-up
How can the greatest common divisor create a canonical hash key for positive, negative, vertical, and horizontal slopes?