# [leetcode] Max Points on a Line

### 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.

First, I thinked out an o(n^3) force solution. It’s workable at last.

However, an o(n^2) solution exists which uses a hash table to store the slope of all lines go through a point.

O(n^3) solution.

1. sort the points by its coordinates o(nlogn)

2. test all possible points. o(n^3)

```//o(n^3) solution
//dx, dy, x1, y1
//(y2 - y1) * dx ==? dy * (x2 - x1)
//will the coordinate be very large? say 2^32?
//Some points are equal.(share same location)

//1. sort points by their x coordinates
//2. count duplicate points

/**
* Definition for a point.
* struct Point {
*     int x;
*     int y;
*     Point() : x(0), y(0) {}
*     Point(int a, int b) : x(a), y(b) {}
* };
*/
class Solution {
public:
int maxPoints(vector<Point>& points) {
//extreme case
if(points.size() <= 2) return points.size();
bool isDuplicate = false;
int max = 0;
int thisMax = 0;
//sort the points by their x coordinate
//sort using a lambda expression
sort(points.begin(), points.end(), [](Point a, Point b){
//bug appeared here
//in first edition
//I only compared a.x and b.x while ignored a.y and b.y
if(a.x < b.x)
return true;
else if(a.x > b.x)
return false;
else{
//a.x == b.x
if(a.y < b.y)
return true;
else
return false;
}
});

for(auto it1 = points.begin(); it1 != points.end() - 1; it1++){//To be improved end() - max
int dx = (*(it1 + 1)).x - (*it1).x;
int dy = (*(it1 + 1)).y - (*it1).y;
if(dx == 0 && dy == 0){
//duplicate points
thisMax++;
}
else{
//not duplicate point
thisMax++;
for(auto it2 = it1 + 1; it2 != points.end(); it2++){
int curThisMax = thisMax + 1;
for(auto it3 = it2 + 1; it3 != points.end(); it3++){
if(((*it3).y - (*it1).y) * ((*it2).x - (*it1).x) == ((*it2).y - (*it1).y) * ((*it3).x - (*it1).x)){
//on a same line
curThisMax++;
}
}
max = curThisMax > max? curThisMax: max;
}
max = thisMax > max? thisMax: max;
thisMax = 0;
}
}
max = thisMax + 1 > max? thisMax + 1: max;
return max;
}
};```

o(n^2) solution

slopeMap stores the slope

```//
/**
* Definition for a point.
* struct Point {
*     int x;
*     int y;
*     Point() : x(0), y(0) {}
*     Point(int a, int b) : x(a), y(b) {}
* };
*/
class Solution {
public:
int maxPoints(vector<Point>& points) {
if(points.size() <= 2) return points.size();
//there is a subtle bug here.
//Accuracy problem.
//What the slop of two lines are very closed but not the same?
unordered_map<double, int> slopeMap;
int maxRe = 0;
for(auto it1 = points.begin(); it1!= points.end(); it1++){
int x = (*it1).x;
int y = (*it1).y;
int duplicateNum = 1;
int nullSlopeNum = 0;
slopeMap.clear();
for(auto it2 = it1 + 1; it2 != points.end(); it2++){
int nx = (*it2).x;
int ny = (*it2).y;
//duplicate point
if(nx == x && ny == y){
duplicateNum++;
}
//slop do not exist
else if(nx == x){
nullSlopeNum++;
}
//ordinary point
else{
double slope = (double)(ny - y) / (nx - x); //type conversion is important!
if(slopeMap.find(slope) == slopeMap.end()){
slopeMap[slope] = 1;
}
else{
slopeMap[slope]++;
}
}
}
int thisMax = 0;
for(auto it = slopeMap.begin(); it != slopeMap.end(); it++){
thisMax = thisMax < it->second? it->second: thisMax;
}
maxRe = max(maxRe, nullSlopeNum + duplicateNum);
maxRe = max(maxRe, thisMax + duplicateNum);
}
return maxRe;

}
};
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.