Any better solution than O(n^2) ?


  • 0
    L

    Any better solution than O(n^2) ?

    Pick 2 points from n. generate a line y=kx+b; store <k,b> in a hashset.


  • 0
    A

    I have the similar idea, but I got two questions:

    1. not all lines could be represented by y = kx + b, e.g. x = 1, so what line representation should we use?
    2. how to write c++ code to store <k,b> in a hashset. So exactly what STL container should we use to hash a pair of double value?

    Thanks a lot!


  • 4
    P

    Storing <k,b> is not a good idea.

    Avoid using y = kx + b.

    Try using ax + by + c = 0.

    I don't know if there is some algorithm running faster than O(N^2). I will be glad to know if someone else does.


  • 0
    P

    to use hashset, use unordered_set; to use hashmap, use unordered_map. In this case, you may have to define a class that do the hash


  • 0
    T

    I converted <k, b> into String by Double.toString(k) + Double.toString(b) (in Java).


  • 0
    P

    how do you deal with the case where <k, b> does not exist


  • 0
    A

    ax + by + c = 0 does look good, but how do you calculate <a,b,c> by only two points? Given (x1,y1) and (x2,y2), there is no unique solution for <a,b,c>.
    Still I hate using double too...


  • 0
    A

    convert whatever <k,b> or <a,b,c> to string for hashing is a smart idea! @tuliren


  • 0
    T

    Because it is string, you can save whatever cases you want. When k does not exist, just store the string "b=..." into the HashSet.


  • 0
    T

    I guess we have to calculate the gcd of a and b, and then do a = a / gcd; b = b / gcd;.


  • 0
    P

    for two points (x0, y0) and (x1, y1) where x0 != x1 or y0 != y1, we can set a = y1 - y0, b = x0 - x1 and c = x1 * y0 - x0 * y1. Then calculate the gcd of a, b and c and divide them by gcd. Then make a becomes non-negative and b non-negative when a is zero


  • 0
    A

    Awesome! @porker2008


  • 0
    W

    Hi Porker, your solution is good. But do we have to find gcd? The only reason to use ax+by+c=0 is to cover the case where b=0.
    When b==0, we always set a=1. When b!=0, we always unify b=1. Then given each possible in 2D map, there is only one unique set of (a,b,c).


  • 0
    P

    You are right, when b is 0, a is always 1; but when b is not 0, we don't always unify b to 1 because a, b, c, must be integers.


  • 0
    W

    Thanks Porker, I did not notice that you are trying to find the integers for <a,b,c>. GCD will make the solution more accurate but it takes higher running time. Is there an efficient way to calculate the GCD for three integers? Appreciate for your sharing.


  • 0
    U

    I don't think storing <k, b> is a good idea, because k, as a float number is not a precise value. Do you got Accepted by using this method ?
    Therefore, I used an O(n^3) algorithm, with dynamic programing which can decrease the average steps number to (n+1)*n*n/4. (the running time in 44 ms)


  • 0
    Y

    how do you handle duplicated points? I cannot figure out a way to handle duplicated points with O(n^2).


  • 0
    U

    Actually, you can reconstruct a new points set as <Point, count> by using unordered_map, which can be done in O(n)


  • 3
    S

    For a line going through two points you can store the deltas in x and y as a representation for the slope of that line (so you have a pair of values per line). To check that two lines (p,q) and (s,t) are parallel using this representation, use the predicate (p * t == q * s). But this does not tell us if they are the same line.

    To check that they are the same line, we need a point in each of them. So instead of storing the deltas, we store the two points that the line goes through.

    struct Line
    { Point p, q; };
    
    Point sub(Point & p, Point & q)
    {   Point s(p.x - q.x, p.y - q.y);
        return s;
    }
    
    int dot(Point p, Point q)
    {   return (p.x * q.x + p.y * q.y);
    }
    
    bool sameLine(Line & L1, Line & L2)
    {   int dx1 = abs(L1.p.x - L1.q.x);
        int dy1 = abs(L1.p.y - L1.q.y);
    
        int dx2 = abs(L2.p.x - L2.q.x);
        int dy2 = abs(L2.p.y - L2.q.y);
    
        if(dx1 * dy2 != dx2 * dy1) return false;
    
        /* At this point, L1 and L2 must be parallel. Are they the same? 
         */
         
        Point p, q;
        
        p = sub(L2.p, L1.q);
        q = sub(L2.q, L1.q);
        
        return (dot(p, q) == 0);
    }
    

    This solution does not use gcd's so it's faster (maybe). It's also accurate.


  • 18
    J

    Inspired by @porker2008, For each point P, we tried to find the line with most points AND containing P. So calculating the slope is enough. It maybe hard to be faster than O(n^2).

    int gcd(int a, int b){
         return a?a/abs(a)*abs(gcd(b%a, a)):b;
     }
    
    int maxPoints(vector<Point> &points) {
        int result=0;
        for(int i=0;i<points.size();i++){
            unordered_map<string,int> count;
            int same=1,mx=0;
            for(int j=i+1;j<points.size();j++){
                int x=points[i].x-points[j].x;
                int y=points[i].y-points[j].y;
                int g=gcd(x,y);
                if(!g){same++;continue;}
                x/=g,y/=g;
                mx=max(mx,++count[to_string(x)+" "+to_string(y)]);
            }
            result=max(result,mx+same);
        }
        return result;
    }
    

Log in to reply
 

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