# C++ O(N^2) solution

• Basically I calculate the equation of every line from the given points.(y = m + b). Then I can compare the equations to see if any points fall on the same line. How I handle duplicates is to first go through the input and remove all duplicate values and record the count in a hashtable. One issue i ran into using Float to calculate slope is if to values are very close to 0 (+-.0005) they will have different slopes. So I do some small rounding around 0 to handle this case. Curious what other think of this solution. I left plenty of comments in the code.

``````#include <unordered_map>
#include <vector>
#include <string>

using namespace std;
class Solution {
public:
int maxPoints(vector<Point> &points) {
if(points.size() <= 2) //size is less then or equal to 2 then just return size
return points.size();

unordered_map<string, int> dupMap;
for(int i = 0; i < points.size(); i++){ // delete dubs and keep track of their count in dupMap
string pt = to_string(points[i].x) + ' '+ to_string(points[i].y);
if(dupMap.count(pt) == 0)
dupMap[pt] = 0;
else{
dupMap[pt]++;
points.erase(points.begin() + i--);
}
}

if(points.size() == 1){ //if every item  was a dup
string pt = to_string(points[0].x) + ' '+ to_string(points[0].y);
return dupMap[pt] + 1;
}

int max = 2;
for(int i = 0; i < points.size()-1; i++){//O(N^2) calclate every combination of points
unordered_map<string, int> hashMap;
string pt = to_string(points[i].x) +' '+ to_string(points[i].y);

for(int j = i+1; j < points.size(); j++){
string pt2 = to_string(points[j].x) +' '+ to_string(points[j].y);
string eq = "";
if(points[i].x == points[j].x)
eq = "x = " + to_string(points[i].x); //infinte slope
else{
float m = (float)(points[j].y - points[i].y) / (float)(points[j].x - points[i].x);//slope
m = (m < 0.0005 && m > -0.0005)? 0: m; //rounding to 0 for floats
float b = (float)points[i].y - (float)(m * points[i].x);
eq = "y =" + to_string(m) + '+' + to_string(b); //form equation string
}

if(hashMap.count(eq) == 0){ //havent seen this eq before
hashMap[eq] = 2;
if(dupMap[pt] > 0) //pt has dupes
hashMap[eq] += dupMap[pt];
if(dupMap[pt2] > 0)//pt2 has dupes
hashMap[eq] += dupMap[pt2];
}
else
hashMap[eq] += (dupMap[pt2] > 0)? dupMap[pt2] + 1 : 1;
max = (hashMap[eq] > max)? hashMap[eq] : max;
}
}
return max; //return the max count
}
``````

};

I use a new structure newPoint which contains x,y,n. and n is the number of duplication.

I have a good idea. Using integer only! **
Firstly define int variable "up" and "down". up <- pt2.y-pt1.y; down <- pt2.x-pt1.x;
then we know that slop rate k should be up/down.
Thus if we want to judge if k1 equals k2,
we only need to compare
if( k1.up
k2.down == k2.up
k1.down) is true then we know k1 equals k2;
Since all operation are only multiplication and plus on integers. it's fast and robust.

the rest are same

• ACCEPTED:
A very simple O(N2) solution

Logic : Finding maximum points with similar slopes with all NC2 pairs taken into consideration

``````class Solution {
public:
int getmax(vector<Point> arr)  // counts similar slope of all n-1 points with respect to arr[0]  :
{
map<float,int> mp;
float m,dy,dx;
int extra;                  // Takes care of duplicate points
int max=0;
extra=1;
for(int i=1 ; i<arr.size() ; i++)
{
dy=arr[i].y-arr[0].y;
dx=arr[i].x-arr[0].x;
if(dx==0 && dy==0)
extra++;
else
{
m=(dx!=0)?(dy/dx):(float)INT_MAX;
mp[m]++;
}

}

map<float,int> ::iterator i;

for(i=mp.begin() ; i!=mp.end() ; i++)
if(i->second>max)
max=i->second;

return max+extra;

}

int maxPoints(vector<Point> &points) {
int n=points.size();

if(n<=2)
return n;

int max,temp_max;
Point temp;
max=2;
for(int i=0 ; i<n; i++)
{
temp=points[0];       // Swapping takes care of all NC2 points being examined
points[0]=points[i];
points[i]=temp;

temp_max=getmax(points);
if(temp_max>max)
max=temp_max;
}

return max;

}
};``````

• Nice algorithm!

A minor suggestion. The running time of your implementation could be cut into half, by enumerating only n (n - 1) / 2 pairs, rather than n * (n - 1).

For example. Suppose p1, p2, p3 are locating in the optimal line. Your first loop could enumerate some boundary point in this line and get the optimal result, namely three points, regardless of any order of p1, p2, p3 given in advance.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.