16ms/28ms C++ Solutions with Explanations


  • 27

    This problem has a naive idea, which is to traverse all possible pairs of two points and see how many other points fall in the line determined by them. This idea is of O(n^3) time complexity and will meet TLE.

    Well, let's focus on lines instead of pairs of points. Could we just find out how many points fall in all possible lines? The answer is yes. Remember that a line is determined by its slope and intercept. In fact, if two lines with the same slope share a common point, then they are just the same line. So to determine a line, we need its slope and a point.

    Now comes the idea to solve this problem. We start from a specific point p, and compute all the slopes of the lines between p and the remaining points. Then those with the same slopes will be the same line. We can find out the maximum number of points fall on a line containing p. We exhaust all possible p's and record the largest number we have seen. This number is just answer.

    Well, there are still two special cases to handle:

    1. Duplicate points: a pair of duplicate points give no determined line, so we just count the number of duplicates and add them to the result.
    2. Vertical lines: the slope of these lines is infinity mathematically. We simply set it to be INT_MAX in the following code.

    Now we have the following code, using an unordered_map<float, int> slopes to record how many points fall in the line of a specific slope and containing points[i]. Since all the operations of unordered_map is O(1), this code is of O(n^2) complexity.

    class Solution {
    public:
        int maxPoints(vector<Point>& points) {
            unordered_map<float, int> slopes;
            int maxp = 0, n = points.size();
            for (int i = 0; i < n; i++) {
                slopes.clear();
                int duplicate = 1;
                for (int j = i + 1; j < n; j++) {
                    if (points[j].x == points[i].x && points[j].y == points[i].y) {
                        duplicate++;
                        continue;
                    }
                    float slope = (points[j].x == points[i].x) ? INT_MAX : 
                                  (float)(points[j].y - points[i].y) / (points[j].x - points[i].x);
                    slopes[slope]++;
                }
                maxp = max(maxp, duplicate);
                for (auto slope : slopes)
                    if (slope.second + duplicate > maxp) 
                        maxp = slope.second + duplicate; 
            }
            return maxp;
        }
    };
    

    Well, since the representation of floating point numbers is sometimes inaccurate, we may use a more safer way to represent the slope (dy / dx), which is to record dx and dy in a pair<int, int>. However, once we use pair<int, int> for the key of the map, we cannot use an unordered_map since pair<int, int> is unhashable. We now change to map and the time complexity becomes O(n^2logn). Also, since dy = 4, dx = 2 and dy = 8, dx = 4 represents the same slope, we need to divide both of them by their gcd first.

    The code is as follows. The logic is the same of the one above, just introducing pair and gcd.

    class Solution { 
    public: 
        int maxPoints(vector<Point>& points) {
            map<pair<int, int>, int> slopes;
            int maxp = 0, n = points.size();
            for (int i = 0; i < n; i++) {
                slopes.clear();
                int duplicate = 1;
                for (int j = i + 1; j < n; j++) {
                    if (points[j].x == points[i].x && points[j].y == points[i].y) {
                        duplicate++;
                        continue;
                    }
                    int dx = points[j].x - points[i].x;
                    int dy = points[j].y - points[i].y;
                    int dvs = gcd(dx, dy);
                    slopes[make_pair(dx / dvs, dy / dvs)]++;
                }
                maxp = max(maxp, duplicate); 
                for (auto slope : slopes)
                    if (slope.second + duplicate > maxp)
                        maxp = slope.second + duplicate;
            } 
            return maxp;
        }
    private:
        int gcd(int num1, int num2) {
            while (num2) {
                int temp = num2; 
                num2 = num1 % num2;
                num1 = temp;
            }
            return num1;
        }
    };

  • 0
    B

    (dx=-2, dy=3) and (dx=2, dy=-3) will be treated as two lines in your code? How about (dx=-2, dy=-3) and (dx=2, dx=3)?


  • 0
    S

    [[0,0],[1,2147483647],[0,1]] would fail.

    Your input

    [[0,0],[1,2147483647],[0,1]]

    Your answer

    3

    Expected answer

    2


  • 1
    W

    @jianchao.li.fighter Two improvements

    • We can still use unordered_map as long as we provide our own hash : )
    struct myhash {
            size_t operator()(const pair<int,int>& p) const {
                return p.first ^ p.second * 3;
            }
        };
    
    • More concise GCD method
    int gcd(int a, int b) {
            return b == 0 ? a : gcd(b, a % b);
        }
    

  • 0
    N

    @jianchao-li-fighter The first version cannot pass with the input [0,0], [94911151, 94911150], [94911152, 94911151], which outputs the wrong answer 3. Is this because the using of "float" as the map key, which causes problem when calculating the slope? Thanks a lot.


  • 0
    S

    What if you have two different vertical lines with different x, are you putting all of them in to the INT_MAX bin?


  • 0
    B

    @jianchao.li.fighter Great concise code! So I thought I was being clever, and used a string instead of a pair to store the key, so that I can use unordered_map, instead of map. However, my supposedly O(n^2) code took 20ms vs the 6ms of your O(n^2logn) code. If anyone knows why, would love to hear your thoughts, thanks!

    class Solution {
    public:
        int maxPoints(vector<Point>& points) {
            int div, res=0, n=points.size();
            unordered_map<string,int> slopes;
            
            for (int i=0; i<n; i++) {
                int self=1;
                slopes.clear();
                slopes["dummy"]=0; // takes care the case of a single point
                
                for (int j=i+1; j<n; j++) {
                    Point &a=points[i], &b=points[j];
                    
                    if (a.x==b.x && a.y==b.y) self++;
                    else if (a.x==b.x) slopes["vertical"]++;
                    else {
                        div=gcd(a.y-b.y,a.x-b.x);
                        string key=to_string((a.y-b.y)/div)+' '+to_string((a.x-b.x)/div);
                        slopes[key]++;
                    }
                }
                
                for (auto p:slopes) res=max(res,p.second+self);
            }
            
            return res;
        }
    private:
        int gcd(int num1, int num2) {
            int temp;
            while (num2) {
                temp=num2;
                num2=num1%num2;
                num1=temp;
            }
            return num1;
        }
    };
    

Log in to reply
 

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