149. Max Points on a Line
You receive points, a list of n distinct points on the 2D plane, where points[i] = (x_i, y_i). Return one integer: the largest number of these points that sit together on a single straight line.
A lone point counts as 1 and any two points always define a line, so the answer for n <= 2 is n — the interesting work starts at three. Watch out for vertical lines (infinite slope) and for slopes like 2/4 and 1/2 that look different but are the same direction.
Example 1:
Input: points = [(1,1), (2,2), (3,3)]
Output: 3
Explanation: All three points sit on the line y = x, so the answer is 3.
Example 2:
Input: points = [(1,1), (3,2), (5,3), (4,1), (2,3), (1,4)]
Output: 4
Explanation: The line y = 5 − x passes through (1,4), (2,3), (3,2) and (4,1) — four points. The best any other line manages is three, e.g. (1,1), (3,2), (5,3).
Constraints:
- 1 ≤ n ≤ 300
- -10⁴ ≤ x, y ≤ 10⁴
- All points are distinct.
Hints:
Fix one point as the anchor. Every other point lies on exactly one line through the anchor, identified purely by its direction from the anchor. Count how many points share each direction with a hash map; the biggest bucket plus the anchor itself is the best line through that anchor.
Never hash floating-point slopes — precision will betray you. Reduce the direction vector (dx, dy) by their gcd and normalize the sign (force dx > 0; for vertical lines use (0, 1)) so every point on the same line through the anchor produces the identical key.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: points = [(1,1), (2,2), (3,3)]
Expected output: 3