A c++ integer solution with sorting, caching, bounds checking


  • 0
    T

    This solution takes about 60 ms. The complexity is O(n^2).

    1. It uses GCD of dx and dy to normalize the slope and to represent it with normalized (dx, dy), as mentioned in other solutions.
    2. It sorts points on their x coordinates to put them into bins (of same x); points in each bin are sorted on their y coordinates. This transform defines the order in which I traverse lines and also generates several useful properties: (a) the closure box the all points; (b) number of points of vertical lines; (c) when I draw a non-vertical line from left to right, every vertical bin on its way adds no more than one unique point -- therefore I know the maximum number points a particular bin can add to a line; (d) when I traverse the plane from left to right, I know the upper bound of the number points the rest bins may add to a line.
    3. I define lines with their first and second point from the left P0(x0, y0) and P1(x1, y1). I traverse all possible non-vertical lines in the following order: select P0 following sorted order (left to right, bottom to top) and select P1 from the bins right to P0's bin and also following the same order.
    4. I extend a line from P1 to the right by crossing other bins. Checking if one bin contains a point on the given line is O(1) as bin is sorted.
    5. With the sorting, I do the following two bounds checking and bail out earlier: (a) since I extend lines from left to right, I stop when it exceeds the closure box; (b) based on 2.c and 2.d, I stop when I see no enough points left to beat the existing result.
    /**
     * 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 GCD(int x, int y) const {
            x = abs(x);
            y = abs(y);
            if(x == 0 && y == 0) return 1;
            if(x == 0) return y;
            if(y == 0) return x;
            while(x%y) {
                int newy = x%y;
                x = y;
                y = newy;
            }
            return y;
        }
        
        int maxPoints(vector<Point>& points) {
            if(points.size() < 3) return points.size();
            map<int, map<int, int> > sorted; // sort points with x coordiantes first, then with y coordinates
            vector<pair<int, int> >xs;  // every element's first is a x coordinate; second is the upperbound
                                        // of number points on non-vertical lines that are left to (x, *) 
            int maxCounter = 0;
            
            Point minPt(numeric_limits<int>::max(), numeric_limits<int>::max());
            Point maxPt(numeric_limits<int>::min(), numeric_limits<int>::min());
    
            // sort points and find the closure box of all points
            for(auto pt : points) {
                if(pt.x < minPt.x) minPt.x = pt.x;
                if(pt.y < minPt.y) minPt.y = pt.y;
                if(pt.x > maxPt.x) maxPt.x = pt.x;
                if(pt.y > maxPt.y) maxPt.y = pt.y;
                
                sorted[pt.x][pt.y] = sorted[pt.x][pt.y]+1;
            }
            // fill xs
            int acc = 0;
            for(auto ptxit = sorted.rbegin(); ptxit != sorted.rend(); ++ptxit) {
                int sum = 0;
                int maxNum = 0;
                for(auto y : ptxit->second) {
                    sum += y.second;
                    maxNum = max(y.second, maxNum);
                }
                acc += maxNum;
                xs.push_back(make_pair(ptxit->first, acc));
                maxCounter = max(sum, maxCounter);
            }
            reverse(xs.begin(), xs.end());
            
            // cache element is accessed as cache[x][y][dx][dy]
            // cache is organized with key (x, y, slope), where
            // slope is represented with (dx, dy)
            // if a point(x,y) has been checked on a line with slope (dx,dy) 
            // before, we don't need to check the line starting from this point of 
            // the same slope
            map<int, map<int, map<int, set<int> > > > cache;
            
            // find (x0, y0), the first point from left for a line
            // enumerate from left to right for every possible x
            for(auto x0it = xs.begin(); x0it != xs.end(); ++x0it) {
                // the upper bound is already less than existing result
                if(maxCounter >= x0it->second) break;
                int x0 = x0it->first;
                auto y0s = sorted[x0];
                // for every point with same x0 from bottom to top
                for(auto y0Item : y0s) {
                    // we have (x0, y0) now
                    int y0 = y0Item.first;
                    // find (x1, y1), the second left point on the line
                    // for every x1 greater than x0 from left to right
                    for(auto x1it = x0it + 1; x1it != xs.end(); ++x1it) {
                        // the upper bound is already less than existing result
                        if(maxCounter >= sorted[x0][y0] + x1it->second) break;
                        int x1 = x1it->first;
                        auto y1s = sorted[x1];
                        for(auto y1Item : y1s) {
                            // we have (x1, y1) and a line now
                            int y1 = y1Item.first;
    
                            // calculate normalized scope and represent it with (dx, dy) to avoid floating point
                            int dy = y1 - y0, dx = x1 - x0;
                            int gcd = GCD(dx, dy);
                            dy /= gcd; dx /= gcd;
    
                            // check if this point has been found on a line before
                            if(cache[x0][y0][dx].find(dy) != cache[x0][y0][dx].end()) continue;
                            int counter = sorted[x0][y0] + sorted[x1][y1];
                            // extend the line (x0, y0) (x1, y1) to the right, but only chek the x cooridates 
                            // available in points
                            for(auto x2it = x1it + 1; x2it != xs.end(); ++x2it) {
                                // the upper bound is already less than existing result
                                if(maxCounter >= counter + x2it->second) break;
                                int x2 = x2it->first;
                                if((x2 - x0) % dx != 0) continue;  // if y2 of (x2, y2) on the current line is not an integer
                                
                                int y2 = dy * (x2 - x0) / dx + y0; // this division won't result in fraction
                                if(y2 > maxPt.y || y2 < minPt.y) break;  // if it is alreay out of the closure box
                                auto y2s = sorted[x2];
                                if(y2s.find(y2) != y2s.end()) {
                                    // found one
                                    counter += sorted[x2][y2];
                                    // cache the point with slope to avoid checking it again
                                    cache[x2][y2][dx].insert(dy);
                                }
                            }
                            maxCounter = max(counter, maxCounter);
                        }
                    }
                }
            }
                
            return maxCounter;
        }
    
    };

Log in to reply
 

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