C++ O(n^2) solution for your reference


  • 58
    Y

    Hint by @stellari

    "For each point pi, calculate the slope of each line it forms with all other points with greater indices, i.e. pi+1, pi+2, ..., and use a map to record how many lines have the same slope (If two lines have the same slope and share a common point, then the two lines must be the same one). By doing so, you can easily find how many points are on the same line that ends at pi in O(n). Thus the amortized running time of the whole algorithm is O(n^2)."

    In order to avoid using double type(the slope k) as map key, I used pair (int a, int b) as the key where a=pj.x-pi.x, b=pj.y-pi.y, and k=b/a. Using greatest common divider of a and b to divide both a, b ensures that lines with same slope have the same key.

    I also handled two special cases: (1) when two points are on a vertical line (2) when two points are the same.

    class Solution {
    public:
        int maxPoints(vector<Point> &points) {
            
            if(points.size()<2) return points.size();
            
            int result=0;
            
            for(int i=0; i<points.size(); i++) {
                
                map<pair<int, int>, int> lines;
                int localmax=0, overlap=0, vertical=0;
                
                for(int j=i+1; j<points.size(); j++) {
                    
                    if(points[j].x==points[i].x && points[j].y==points[i].y) {
                        
                        overlap++;
                        continue;
                    }
                    else if(points[j].x==points[i].x) vertical++;
                    else {
                        
                        int a=points[j].x-points[i].x, b=points[j].y-points[i].y;
                        int gcd=GCD(a, b);
                        
                        a/=gcd;
                        b/=gcd;
                        
                        lines[make_pair(a, b)]++;
                        localmax=max(lines[make_pair(a, b)], localmax);
                    }
    
                    localmax=max(vertical, localmax);
                }
                
                result=max(result, localmax+overlap+1);
            }
            
            return result;
        }
    
    private:
        int GCD(int a, int b) {
            
            if(b==0) return a;
            else return GCD(b, a%b);
        }
    };

  • 22
    G

    Nice solution indeed. Using gcd is much better than using a floating point number to represent the slope.

    I have a couple of comments:

    1. map in cpp is actually based on binary trees. So the time complexity is O(n^2log(n)).
      In a map the elements are in ascending order according to the value of the keys. So do you know how the comparison between 2 pairs of integers are implemented?

    2. we can change the map to unordered_map by doing

      struct hashfunc
      {
      size_t operator() (const pair<int,int>& l) const
      { return l.first ^ l.second; }
      };

      unordered_map< pair< int,int >,int,hashfunc> lines;

    3. It is not necessary to count the vertical lines separately. That's not a corner
      case using your algorithm. The pair for all vertical lines is simply [1,0].


  • 2
    J

    Does this take care of the case where a->b and c->d have the same slope but they're not on the same line? For example: a(0,0), b(1,1), c(0,3), d(1,4) ?


  • 0
    Y

    "For each point pi, calculate the slope of each line it forms with all other points with greater indices, i.e. pi+1, pi+2, ...."

    So there are always one same shared end for each line formed in one iteration.

    "If two lines have the same slope and share a common point, then the two lines must be the same one"


  • 0
    Z

    Thanks GuaGua. For comment 2 the hasher looks do not work for several cases:

    1. Horizontal and vertical: make_pair(1, 0) and make_pair(0, 1)
    2. make_pair(1, 3) and make_pair(3, 1)

    we may have to think of a better hasher or use map which does not require the hasher


  • 0
    Y

    great idea that use GCD instead of double to express the "line".
    for the map of pair, can we just simply use the "string" as the map key?
    for exmaple, if the a=23, b=19, the make_pair(a,b) just return the string as "23,19"


  • 0
    F

    Hi,
    Very impressive idea about using GCD. But I doubt that if your GCD implementation can work properly. What is the output of GCD(0, -5)? In my computer, it crashes when calculating 0 % -5. Thanks very much!


  • 1
    R

    the whole algorithm is O(n^2 * log(sumSlope))!


  • 0
    E

    Nice, very careful algorithm to this question. I want to ask about this section:
    result=max(result, localmax+overlap+1);
    why we should add 1 at last? localmax+overlap+1....
    Thank you very much.


  • 1
    I

    There are two points, one is the outer loop index by i, and one is the inner loop index by j.
    Because we use one point to compare with others but we have't count, so after the inner loop we add 1.
    overlap is for the same points with the outer loop point.


  • 0
    B

    We might have forgotten that when computing the slope pair, a and b might overflow. Consider two points: A(0, -1), B(0, INT_MAX), then a = 0 and b = INT_MAX + 1; (As stated in the answer blow, don't have to deal with vertical case separately). Thus all variables dealing with slope should use the long type, including pair, a, b, and GCD.


  • 0
    Z
    This post is deleted!

  • 0
    Z

    I think that we can concatenate two integers into one string and use the string as the hash key.

    class Solution 
    {
        // Get the greatest common divisor of two non-negative integers via Euclidean algorithm.
        int GCD(int a, int b)
        {
            while (b != 0)
            {
                int tmp = b;
                b = a%b;
                a = tmp;
            }
           
            return a;
        }
       
    public:
        int maxPoints(vector<Point> &points)
        {
            int cntPoints = points.size();
            // If there are no more than 2 points, return the number of points.
            if (cntPoints <= 2)
            {
                return cntPoints;
            }
           
            int maxCntPoints = 2;
            // For each node i, get all the lines starting from node i to some node j (j > i).
            for (int i = 0; i < cntPoints - 1; i++)
            {
                // Each line starting from node i have a unique representation like a*x + b*y
                // where a and b have been divided by their greatest common divisor. In other
                // words, the slope of the line starting from node i is determined by a and b.
                // The key of this map is (a, b) and the value of this map is count of lines
                // starting from node i with the slope (a, b).
                map<pair<int, int>, int> cntLineMap; 
                int cntNodei = 1;
                int maxCntLines = 0;
               
                for (int j = i + 1; j < cntPoints; j++)
                {
                    if ((points[j].x == points[i].x) && (points[j].y == points[i].y))
                    {
                        // j is a duplicate to i.
                        cntNodei++;
                    }
                    else
                    {
                        // Calculate the slope (a, b) of the line connecting i and j.
                        pair<int, int> slope(points[j].x - points[i].x, points[j].y - points[i].y);
                        // Euclidean algorithm can be only applied to non-negative integers.
                        int gcd = GCD(abs(slope.first), abs(slope.second)); 
                        if (slope.first < 0)
                        {
                            // Make sure that after being divided by gcd, a is always non-negative.
                            gcd = -gcd;
                        }
                        else if ((slope.first == 0) && (slope.second < 0))
                        {
                            // Make sure that if a == 0, b is always non-negative after being divided by gcd.
                            gcd = -gcd;
                        }
                        slope.first /= gcd;
                        slope.second /= gcd;
                        
                        // Add slope to the map cntLineMap. 
                        // (1) If the slope didn't exist in the map, insert a new element with count value 1; 
                        // (2) otherwise, increase the count value by 1.
                        cntLineMap[slope]++;
                        
                        if (cntLineMap[slope] > maxCntLines)
                        {
                            maxCntLines = cntLineMap[slope];
                        }
                    }
                }
                
                if (cntNodei + maxCntLines > maxCntPoints)
                {
                    maxCntPoints = cntNodei + maxCntLines;
                }
            }
           
            return maxCntPoints;
        }
    };

  • 0
    C

    how about (first ^ ~100007) | (second ^ 100007)
    or more crazy, [(first & ~100007) | (second & 100007)] ^ [(first & 100007) | (second & ~100007)]


  • 0
    O

    have your considered the complexity of GCD?


  • 0
    S

    As sumSlope is finite, say to less than INT_MAX, we can consider log(sumSlope) as constant complexity. So the whole complexity is still O(n^2).


  • 0
    L

    nice solution. same idea, looks more concise.

    int maxPoints(vector<Point>& points) {
        unordered_map<double, int> slope;
        int i = 0, max_p = 0, same_p = 1, same_v = 1;
        for (i = 0; i < points.size(); same_p = 1, same_v = 1, i++) {
            for (int j = i+1; j < points.size(); j++) {
                if (points[i].y == points[j].y) 
                    { if (++same_v && points[i].x == points[j].x && ++same_p); }
                else 
                    slope[double(points[i].x - points[j].x) / double(points[i].y - points[j].y)]++;
            }
            max_p = max(max_p, same_v);
            for (auto item : slope) 
                { max_p = max(max_p, item.second + same_p); }
            slope.clear();
        }
        return max_p;
    }

  • 0
    Z

    Why can't just use double instead of GCD?


  • 0
    N

    what's this magic number 100007?


  • 0
    W

    @Yoursong 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;
            }
        };
    

Log in to reply
 

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