108. Most Points in a Line
A drone survey records sensor positions in points, where points[i] = [x, y] gives integer coordinates on a flat field. Several sensors may be installed at exactly the same position, and each one is counted separately.
Return the largest number of sensors that lie on one common straight line. The line may have any direction, including vertical and horizontal. A single sensor always lies on some line, and any two sensors lie on a line together, and sensors at identical positions always share a line.
Example 1
- Input:
- points = [[0,0],[2,2],[5,5],[1,7]]
- Output:
- 3
- Explanation:
The first three sensors lie on the diagonal y = x; the fourth is off that line.
Example 2
- Input:
- points = [[1,1],[1,1],[4,9]]
- Output:
- 3
- Explanation:
The two sensors at (1,1) share a position, and together with (4,9) all three lie on one line.
Example 3
- Input:
- points = [[0,0],[1,2],[3,1],[5,5]]
- Output:
- 2
- Explanation:
No three of these sensors are collinear, so the best line holds only 2.
Constraints
1 ≤ points.length ≤ 2000
points[i].length == 2
-1000 ≤ x, y ≤ 1000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 6,000 msC++ 1,500 msJava 3,000 msJavaScript 3,000 msTypeScript 3,000 ms
Expected complexity
- Time
- O(n^2)
- Space
- O(n)