# 149. Max Points on a Line
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
Example 1:
Input: [[1,1],[2,2],[3,3]]
Output: 3
Explanation:
^
|
| o
| o
| o
+------------->
0 1 2 3 4
Example 2:
Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation:
^
|
| o
| o o
| o
| o o
+------------------->
0 1 2 3 4 5 6
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.
# Solution
Approach 1: For each point, calculate the slope of each other point with it.
# Code (Python)
Approach 1:
# Code (C++)
Approach 1:
class Solution {
private:
int getGCD(int a, int b) {
if (b == 0)
return a;
return getGCD(b, a % b);
}
public:
int maxPoints(vector<vector<int>>& points) {
int n = points.size();
if (n == 0)
return 0;
int res = 0;
for (int i = 0; i < n; ++i)
{
int x1 = points[i][0];
int y1 = points[i][1];
int dup = 1;
int subRes = 0;
unordered_map<double,unordered_map<double,int>> umap;
for (int j = i + 1; j < n; ++j)
{
int x2 = points[j][0];
int y2 = points[j][1];
if (x1 == x2 && y1 == y2)
{
dup++;
}
else
{
int diffX = x2 - x1;
int diffY = y2 - y1;
int diffGCD = getGCD(diffX, diffY);
diffX /= diffGCD;
diffY /= diffGCD;
umap[diffX][diffY]++;
subRes = std::max(subRes, umap[diffX][diffY]);
}
}
res = std::max(res, subRes + dup);
}
return res;
}
};