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


  • 2
    O
    /**
     * 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!


  • 0
    D

    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.


  • 4
    L

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


  • 0
    O

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


  • 0
    D

    great catch!


Log in to reply
 

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