# 149 Max Points on a Line

Given an array of `points` where `points[i] = [xi, yi]` represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.

Example 1:

``````4
3     x
2   x
1 x
0 1 2 3 4

Input: points = [[1,1],[2,2],[3,3]]
Output: 3
``````

Example 2:

``````4 x
3   x     x
2     x
1 x     x
0 1 2 3 4 5

Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
``````

Constraints:

• `1 <= points.length <= 300`
• `points[i].length == 2`
• `-104 <= xi, yi <= 104`
• All the `points` are unique.

For a fixed point `points[i]`, consider all other points `points[j]` and calculate the atan2 for each vector `points[j] - points[i]` (the vector with the magnitudes `(points[j].x - points[i].x, points[j].y - points[i].y)`). Then find the maximum number of times some angle value occurs among the calculated values.

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 `````` ``````class Solution: def maxPoints(self, points: List[List[int]]) -> int: n = len(points) if n == 1: return 1 result = 2 for i in range(n): cnt = collections.defaultdict(int) for j in range(n): if j != i: cnt[math.atan2(points[j] - points[i], points[j] - points[i])] += 1 result = max(result, max(cnt.values()) + 1) return result``````