# My java accepted solution for your reference (only using array).

• ``````    public class Solution
{
public int maxPoints(Point[] points)
{
int n=points.length;
if (n<2) return n;
int currentL=0,maxL=2,x=0,y=0,dx=0,dy=0,overlap=0,upperB=n;
for(int i=0; i<upperB; i++)
{
for(int j=i+1; j<n; j++)
{
currentL=1;
/*
* Given two points: (a,b) and (c,d), the corresponding normal vector is (b-d,c-a)
* If another point (s,t) is in the same line uniquely defined by (a,b) and (c,d),
* then (s-a,t-b) dot (b-d,c-a) = 0
*/
x=points[i].y-points[j].y;
y=points[j].x-points[i].x;

/* If two points are the same, there is no need to check further,
* since a line has to be defined by exactly two distinct points.
*/
if(x==0 && y==0)
overlap++;

/* Well, it might be the case that duplicates are not consecutive,
* but as long as we can have a non-trivial normal vector, it won't matter.
*/
else
{
currentL++;

/*  Explaining (currentL+n-k>maxL):
*  no further checking is necessary when there isn't enough left to make it surpass maxL.
*/
for(int k=j+1; k<n && currentL+n-k>maxL; k++)
{
dx=points[k].x-points[i].x;
dy=points[k].y-points[i].y;
if(x*dx+y*dy==0)
currentL++;
}
}
maxL=Math.max(currentL+overlap,maxL);
}

/* Explaining (upperB=n-maxL):
* it would be crystal clear as soon as you draw a table for combinations of case n>3.
*/
upperB=n-maxL;
overlap=0;
}
return maxL;
}
}``````

• superb, clean code and clear explaination

• You solution costs time O(n^3). However, the best solution that use map to count slope costs O(n^2 lgn).

• Which is true, but I have to say that, since I applied two pruning methods, for the most of cases, it achieves the similar or even better performance than ones using map. Also, mine is more memory efficient.

• ``````int maxPoints(vector<Point> &points)
{
int res=0;
for(int i=0;i<points.size();i++){
int dup=1;
map<double, int> mp;
for(int j=i+1;j<points.size();j++){
if(points[i].x==points[j].x && points[i].y==points[j].y)
dup++;
else if(points[i].x==points[j].x)
mp[INT_MAX]++;
else{
double key=double(points[i].y-points[j].y)/double(points[i].x-points[j].x);
mp[key]++;
}
}
map<double, int>::iterator iter;
int max=0;
for(iter=mp.begin();iter!=mp.end();iter++)
max=max<iter->second?iter->second:max;
max+=dup;
res=res<max?max:res;
}
return res;
}
``````

Here is my solution. It seems not that accurate in some floating point cases, but it works well on OJ. And it takes 80ms.

• I just write it in C++ by only changing .length to .size() and Math.max to max. I achieved 48 ms performance.

• You can try it out.

• My question is looks like you only take slope of the line as key. How do you handle the case that two lines have same slope but different intercept (intersection on y-axis)?

• After each inner loop, he reset the haspmap

• The best solution should be O(n^2). Using map to count the slope appearance.

• @kecen agreed, and we dont have to worry about `Double` as the key of hashmap.

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