Why it works
- Two lines through the same point p with the same slope are one line. So the points after p that share a slope with it lie on one line with p, and the map counts them.
- The slope is kept as a reduced fraction dy/dx, not as a division: 4/2 and 2/1 become one key, there is no rounding, and a vertical line is just 1/0.
- A line through an earlier point was already counted when that point was p, so each p only looks at the points after it.
Complexity
Time O(n²): every pair of points is looked at once (reducing the fraction adds a short gcd). Memory O(n): the map holds at most n − 1 slopes.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗