Last Executed Input: test data is blank


  • 2
    T

    I'm getting Time Limit Exceeded for my solution.
    However, the test case it correspondingly shows is empty (Unlike cases, in which empty vectors/containers are passed in & displayed as [ ]).

    Last executed input:

    Any ideas what wrong ?

    Updated ques with code 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 {
        bool samePt(Point a, Point b){
            return (a.x == b.x) && (a.y == b.y);
        }
    
    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.
            if(points.size() <= 2)  return points.size();
            int maxPtsOnLine = 2;
            for(Point w: points){
                for(Point z: points){
                    int thisLinePts = 2;
                    if(!samePt(w, z)){
                        for(Point u: points){
                            if(!samePt(w, u) && !samePt(z, u)){
                                if((w.y - z.y)*(z.x - u.x) == (w.x - z.x)*(z.y - u.y)){
                                    ++thisLinePts;
    
                                    maxPtsOnLine = max(thisLinePts, maxPtsOnLine);
                                }
                            }
                        }
                    }
                }
            }
    
            return maxPtsOnLine;
        }
    };

  • 0
    P
    /**
     * 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 {
        bool samePt(const Point& a, const Point& b){ /* Avoid copying */
            return (a.x == b.x) && (a.y == b.y);
        }
    
    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.
            if(points.size() <= 2)  return points.size();
            int maxPtsOnLine = 2;
            for(Point& w: points){
                int samepoints = 0; /* Calculate the number of same points */
                for(Point& z: points){
                    int thisLinePts = 0; /* Calculate the number of the points in same line */
                    if(!samePt(w, z)){
                        for(Point& u: points){
                            if((w.y - z.y)*(z.x - u.x) == (w.x - z.x)*(z.y - u.y)){
                                ++thisLinePts;
                            }
                        }
                        maxPtsOnLine = max(thisLinePts, maxPtsOnLine);
                    } else {
                        samepoints++; /* If z is the same point as w, increase samepoints */
                    }
                }
                maxPtsOnLine = max(samepoints, maxPtsOnLine);
            }
    
            return maxPtsOnLine;
        }
    };

  • 0

    Sorry, this is a limitation on the Judger side, which will probably be fixed in the future. Most likely it is timeout on a huge input dataset, which won't be too meaningful to you anyway.


  • 0
    T
    This post is deleted!

  • 0
    T

    I've posted my code in answer (since, code formatting isn't preserved in comments)


  • 0

    Please put your code by editing your question, and delete this answer.


  • 0
    T

    According to your code, the time complexity is O(N^3). I guess that leads to a timeout. The solution should be O(N^2).

    In addition, you checked whether two points are the same according to their coordinates. However, in this problem, the current design of the online judge is that points with same coordinates are considered different points. So [(0, 0), (0, 0), (0, 0)] should give an answer of 3. But I think your code will give an answer of 2.


  • 0
    P
    This post is deleted!

  • 0
    P

    O(N^3) is acceptable if you can make your code run fast. =)


  • 0
    M

    time complexity of O(N^3) does not matter.


  • 0
    T

    Thanks, it's a nice fix ! :)


  • 0
    P

    pure bruteforce...
    btw, I did the same thing, but with a bug lol


Log in to reply
 

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