C++ 8ms solution, beaten 100%

• `````` int compare(const void *a, const void *b)
{
if (*(float*)a<*(float*)b) return -1;
if (*(float*)a>*(float*)b) return 1;
return 0;
}

class Solution {
public:
int maxPoints(vector<Point> &points) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
int N = points.size();
if (N<2)
return N;
float slope[N][N];
for (int i=0;i<N;i++)
{
slope[i][i]=-999999;
for (int j=i+1;j<N;j++)
{
if (points[i].x!=points[j].x)
slope[i][j] = float(points[i].y-points[j].y)/float(points[i].x-points[j].x);
else if(points[i].y!=points[j].y)
slope[i][j] = 999999;
else
slope[i][j] = -999999;

slope[j][i] = slope[i][j];
}
}
int MAX = 1,current_len;
float temp;
for (int i=0;i<N;i++)
{
qsort(slope[i],N,sizeof(float),compare);
int j=0,same = 0;
while (slope[i][j]==-999999 && j<N-1)
{
same++;
j++;
}
current_len = same;
if (j<N)
{
current_len++;
temp = slope[i][j];
j++;
}
if (current_len>MAX)
MAX = current_len;
for (;j<N;j++)
{
if (slope[i][j]-temp<0.0001 && slope[i][j]-temp>-0.0001)
{
current_len++;
if (current_len>MAX)
MAX = current_len;
}
else
{
temp = slope[i][j];
current_len=same+1;
}
}
}
return MAX;
}
};``````

• The popular solution is to use a hash to take records of slopes and it's O(n^2).
Roughly speaking,

1. Generates slopes array for each point. Each point has O(n) slopes.
2. For each node's slopes, you qsort them O(n)O(nlogn)
You have O(n^2
logn) time complexity and you are the fastest. Strange.

• I think there are two reasons:

1. His code is actually more like C
2. HashMap is actually not as fast as we think. There are a lot of overhead, and the effect becomes more apparent when N is not that big.

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