30 ms c++ solution with explaination


  • 4
    P
    // LOGIC : sort the points based on x value. Now, calculate the slopes with points after the current 
    // point. Keep on adding to points with same slope. Once done with current points, we ll have a set of slopes m
    // with the number of points with those slopes. Any possible slope having current point is already in the set of slopes.
    // If we take another point say j after i, then we have already calculated points with slope that is between j and i. thus we just need
    // to look after i. 
    class Solution {
    public:
        int maxPoints(vector<Point> &points) {
            auto comp = [] (Point& a, Point& b) { return a.x < b.x; };
            int n = points.size();
            int max_count = 0;
            std::sort(points.begin(), points.end(), comp);
            for (int i = 0; i < n; ++i) {
                unordered_map<double, int> slope_map;
                Point& p1 = points[i];
                int same_point = 1;
                int local_max = 1; // local max to get the number of points passing through max slope line starting at i
                
                // only look for points after the current one since ,
                // we have taken care of line segments before i with j when
                // running iteration for previous values of i
                for (int j = i+1; j < n; ++j) {
                    double m = 0.0;
                    Point& p2 = points[j];
                    if (p1.x == p2.x && p1.y == p2.y) {
                        same_point++;
                        local_max = max(local_max, same_point);
                        continue;
                    } else if (p1.x == p2.x) {
                        m = INT_MAX;
                    } else {
                        m = ((double)(p2.y-p1.y))/(p2.x-p1.x);
                    }
                    if (slope_map.find(m) == slope_map.end()) {
                        slope_map[m] = same_point;
                    }
                    slope_map[m]++;
                    local_max = max(local_max, slope_map[m]);
                }
                max_count = max(local_max, max_count);
            }
            return max_count;
        }
    };

  • 0
    S

    how does your code ditinguish between lines specified by y=2x+1 and y=2x-1 ? they would have the same slope, but correspond to different lines.


  • 0
    C

    line{y = 2x + 1} and line{y= 2x - 1} do not have any common point. So point p[i] cannot be at both of the two lines.


  • 0
    W

    Could you explain the following line in your code? I'm curious about the syntax. Thanks!

    auto comp = [] (Point& a, Point& b) { return a.x < b.x; };


  • 0
    P

    It is lambda function, it compares two given points


  • 0
    P

    Hi, I have used lamda closures which were just introduced in c++11. Check it out. :)


  • 0
    W

    Got it! Thanks you all!


  • 0
    E

    hey, i'm confused about this

    if (slope_map.find(m) == slope_map.end()) {
           slope_map[m] = same_point;
     }
    

    can you help to explain it, very appreciated


  • 0
    P

    (slope_map.find(m) == slope_map.end()) is true when slope_map does not contain m


  • 0
    N

    slope_map[m]++;
    This doesn't check if there are two different lines of the same slope.


Log in to reply
 

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