6-line C++ concise solution, NO double hash key or GCD for slope


  • 4

    The key to this problem is how to characterize "slope" determined by two points. I see many posts here using either a doubleto represent slope or pair<int,int>with GCD process to make it unique. But this either has issues with numerical accuracy or having to do recursive calculation.

    The idea here is to simply define an order of slope in the representation of pair<int,int>:

    Define slope a:=(a.x, a.y)is less than slope b:=(b.x, b.y) if

    • (a.y*b.y > 0)? a.x*b.y < a.y*b.x : a.x*b.y > a.y*b.x.

    Note that this formulation is actually an extension to the traditional slope calculation x/y which not only needs to deal with y == 0as corner case but also unavoidably involves floating point numerical comparison.

    Once the order is defined, it can be used as a key in std::map for counting purpose to gather points along the same line with a reference point, i.e.,

    • define map<Point, int> count with count[Point(x,y)] being the number of points with slope (x,y) to the reference point.

    Note that we count singular slope (0,0) (i.e., duplicated points) separately since this "special" slope is essentially undefined.

    Since an ordered container std::mapis used, the time complexity is O(N^2*logN). The space complexity is O(N)to store map<Point, int> count.

        int maxPoints(vector<Point>& pts) {
            int maxPts = 0;
            for (auto& i:pts) {
              map<Point, int, Comp> count; int dup = 0;
              for (auto& j:pts) maxPts = max(maxPts, i.x==j.x && i.y==j.y? ++dup : (++count[Point(i.x-j.x,i.y-j.y)]+dup));
            }
            return maxPts;
        }
        
        // comparator for key (slope) in map
        struct Comp { 
            bool operator()(const Point& a, const Point& b) { 
              int64_t diff = (int64_t)a.x*b.y - (int64_t)a.y*b.x; // convert to 64bit int for int overflow
              return (int64_t)a.y*b.y>0? diff > 0 : diff < 0;
            } 
        };
    

  • 1

    You still have a bug, though, due to overflow. For example you fail input [[0,0],[65536,65536],[65536,131072]], returning 3 instead of the correct 2. (And the judge solution fails it as well, expecting 3.) (got fixed)


  • 0

    @StefanPochmann said in 6-line C++ concise solution, NO double hash key or GCD for slope:

    [[0,0],[65536,65536],[65536,131072]]

    Yeah, you are right. For variable range in |x| <= MAX, expression f = x1*x2-x3*x4 should be able to handle range |f| <= 2*MAX^2. By definition of struct Point, I modified Comp to convert to int64_t to handle int overflow.

    Thanks for the test case [[0,0],[65536,65536],[65536,131072]] which should have been added to OJ's tests with expected result 2 (instead of 3).

    @administrators


  • 0

    @zzg_zzm Thanks, just added @StefanPochmann 's test case.


  • 0
    L

    Does it work if count[XXX] gets increased first and then dup gets increased? Say count 0 => 10 then dup 0 => 10, maxPts should be 20 instead of 10.


  • 0

    @lxtbell2 said in 6-line C++ concise solution, NO double hash key or GCD for slope:

    Does it work if count[XXX] gets increased first and then dup gets increased? Say count 0 => 10 then dup 0 => 10, maxPts should be 20 instead of 10.

    I get your point. Yes, if the "anchor" point is duplicated with last point in vector pts, we indeed miss some counting. However, this does not matter because we are looping through all points anyway. If not all points are duplicated, we must at some point use an "anchor" point which is not duplicated with pts[N-1] and this will get correct max count at least once, so we can simply update global max count by a single line maxPts = max(maxPts, i.x==j.x && i.y==j.y? ++dup : (++count[Point(i.x-j.x,i.y-j.y)]+dup)) inside double loops.

    Well, I admit that it is not readable...The readable one should count dup and max value in map count[] before updating global max count.

    Readable Version:

        int maxPoints(vector<Point>& pts) {
            int maxPts = 0;
            for (auto& i:pts) {
              map<Point, int, Comp> count; int dup = 0, maxCount = 0;
              for (auto& j:pts) {
                if (i.x==j.x && i.y==j.y) 
                  ++dup; 
                else 
                  maxCount = max(maxCount, ++count[Point(i.x-j.x,i.y-j.y)]);
              }
              maxPts = max(maxPts, maxCount + dup);
            }
            return maxPts;
        }
    

  • 0
    D

    That is even more clever than the GCD in my opinion. Nice.

    Does the map type have an O(n) lookup or O(1) lookup? Curios? Just wondering where the logN came from?


Log in to reply
 

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