Evolve from brute force to optimal


  • 0
    1. O(n^3). To compute the number of points on a line, we need to 1) represent a line and 2) check if a point is on a line. A line determined by two points can be represented by y=kx+b. To check if a point is on the line, we can just bring in the point and check the equation. Then a straightfoward solution is to check all the points for each line.
        int maxPoints(vector<Point>& points) {
            int n = points.size(), mp=0;
            for(int i=0;i<n;i++) {
                int ovlp = 1; //points overlapping with i
                int x = points[i].x, y = points[i].y;
                for(int j=i+1;j<n;j++) {
                    int dx = x - points[j].x, dy = y - points[j].y;
                    int pts = ovlp+1; //points at i + j
                    if(!dx) {
                        if(dy) {
                            for(int p=j+1;p<n;p++) if(x-points[p].x==0) pts++;    
                        } else {
                            ovlp++;  //no line yet
                            continue;             
                        }
                    } else {
                        float k = (float)dy/dx, b = y - k*x;
                        for(int p=j+1;p<n;p++) if(abs(points[p].y - k*points[p].x-b)<0.0001) pts++;
                    }
                    mp = max(pts,mp);
                }
                mp = max(mp,ovlp); // no line
            }
            return mp;
        }
    
    1. O(n^2) A better way to slove the problem is to look at a point at a time, instead of a line. For each point, among all the lines passing through it (each line is determined by this point and another one), we would like to know which one has the max number of points on it. A line can be determined by two points can be represented by a point and a slope. If two lines through a same point has the same slope, it means they are the same line and all the points are on the same line.
        int maxPoints(vector<Point>& points) {
            int n = points.size(), mp=0;
            for(int i=0;i<n;i++) {
                int ovlp = 1;
                unordered_map<float,int> slope;
                for(int j=i+1;j<n;j++) {
                    int dx = points[i].x - points[j].x, dy = points[i].y - points[j].y;
                    if(!dx && !dy) ovlp++;
                    else if (!dx) slope[INT_MAX]++;
                    else slope[(float)dy/dx]++;
                }
                mp = max(mp, ovlp);
                for(auto &p:slope) mp = max(mp,p.second+ovlp);
            }
            return mp;
        }
    
    1. O(n^2logn). Both of the above solutions use float to represent the slope and have precision problems. For example, they both return 3 given [[0,0],[5151,5150]],[5152,5151]]. Change float to double can improve the precision but does not completely solve the problem. The best approach is to use a pair of integers to represnt the numerator and denominator of the slope.
        int maxPoints(vector<Point>& points) {
            int n = points.size(), mp=0;
            for(int i=0;i<n;i++) {
                int ovlp = 1, pts = 0;
                map<pair<int,int>, int> bst;
                for(int j=i+1;j<n;j++) {
                    int x = points[i].x-points[j].x, y=points[i].y-points[j].y;
                    if(!x && !y) {
                        ovlp++;
                        continue;
                    }
                    int d = gcd(x,y);
                    pts = max(pts, ++bst[pair<int,int>(x/d,y/d)]);
                }
                mp = max(mp,ovlp+pts);
            }
            return mp;
        }
        int gcd (int x, int y) {
            return x ? gcd(y%x,x) : y;
        }
    

Log in to reply
 

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