# Help!!! 26/27 passed, can't find bug

• ``````/**
* 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) {
int m, i, j, k, n, m_max=0;
n = points.size();
if (n<=2) return n;
for(i=0;i<n;i++){
m = 1;
for(j=i+1;j<n;j++){
if((points[i].x==points[j].x)&&(points[i].y==points[j].y)) {m++; continue;}
m++;
for (k=j+1;k<n;k++) if (check_collinear(points[i], points[j], points[k])) m++;
m_max = max(m_max, m);
m=1;
}
m_max = max(m_max, m);
}
return m_max;
}

bool check_collinear(Point p1, Point p2, Point p3){
return ((p1.x-p3.x)*(p1.y-p2.y)==(p1.x-p2.x)*(p1.y-p3.y));
}
};
``````

General algorithm - for every pair of pair of points, count how many other points are on the same line.
(caution: if your initial pair has two identical points, you get an extra 'free' collinear point but must proceed until you find a different point to base your comparisons off).

I know O(n^3) when O(n^2) is achievable. But no TLE, and in any case would like to know what's going wrong

Thanks!

• I spent a lot of time on trying to find the issue and didn't have any luck... Don't know why it gave 24 instead of 25. I replied so that I can keep track of the question.

• you miss the point before point[j] which is same as point[i].
for example,
[point a1, point b, point a2(same as a1), point c, point d, point e.]
if the best answer is "a1 a2 d e", your program will run the answer "a1 d e" or "a2 d e".

• Thanks!!! Took me a while to really see it, fix below:

/**

• 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) {
int m, i, j, k, n, m_max=0, n_same;
n = points.size();
if (n<=2) return n;
for(i=0;i<n;i++){
n_same = 0;
m = 1;
for(j=i+1;j<n;j++){
if((points[i].x==points[j].x)&&(points[i].y==points[j].y)) {n_same++; continue;}
m++;
for (k=j+1;k<n;k++) if (check_collinear(points[i], points[j], points[k])) m++;
m_max = max(m_max, m+n_same);
m=1;
}
m_max = max(m_max, m+n_same);
}
return m_max;
}

``````bool check_collinear(Point p1, Point p2, Point p3){
return ((p1.x-p3.x)*(p1.y-p2.y)==(p1.x-p2.x)*(p1.y-p3.y));
}
``````

};

And yes, I am aware that variable names misleading since n_same is not actually a count of number of points identical to point[i], but only of the number of points identical to point[i] before we pick a second, different point[j].

• great catch!

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