Max Points on a Line
Problem
Given a set of distinct points on a 2D plane, return the largest number of them that lie on one straight line.
Examples
Constraints
- • 1 <= points.length <= 300
- • -10^4 <= xi, yi <= 10^4
- • All points are unique
Hints & approach
Hint 1
Fix one anchor point; every line through it is identified by its slope.
Hint 2
Floating-point slopes are unreliable — represent a slope as a reduced fraction.
Hint 3
Divide (dx, dy) by their gcd and normalise the sign so equal directions get equal keys.
Approachtry the hints first
For each anchor point, compute the direction (dx, dy) to every later point, divide both by gcd(|dx|, |dy|), and normalise the sign so opposite directions match (for example make dx positive, or dy positive when dx is 0). Count directions in a hash map; the largest count plus one for the anchor is the best line through that anchor. The overall answer is the maximum across anchors.
Time O(n² log C) · Space O(n)