Solution using string as the key for counting points


  • 0
    L
    class Solution {
        int gcd(int a, int b) {
            if (b!=0) {
                return gcd(b, a%b);
            } else {
                return a;
            }
        }
    public:
        int maxPoints(vector<Point>& points) {
            if (points.size()<3) {
                return points.size();
            }
            int maxCount = 0;
            
            for (auto p1 : points) {
                unordered_map<string, int> counts;
                int maxNoOriginPoints = 0;  // we are calcuating the non-origin points on the same slope based on the "shifted" origin of p1
                for(auto p2 : points) {
                    
                    int dy = p2.y - p1.y;
                    int dx = p2.x - p1.x;
                    
                    int sign = dy*dx >=0 ? 1 : -1;
                    dy = abs(dy);
                    dx = abs(dx);
                    
                    int g = gcd(dy, dx);
                    dy = g == 0 ? dy : dy/g;
                    dx = g == 0 ? dx : dx/g;
                    
                    string key = sign==-1 ? "-":"+";
                    key +=std::to_string(dx) + "_" + std::to_string(dy);
                    counts[key]++;
                    
                    if (dx==0 && dy==0) {
                        continue;   
                    }
                    
                    maxNoOriginPoints = max(maxNoOriginPoints, counts[key]);
                }
    
                maxCount = max(maxCount, maxNoOriginPoints + counts["+0_0"]); // for all connected points on the same line, we should add back the "origin" if it exists, which is the p1 above. e.g for (0,0) and (1,1), there should be 2 points on the same line
            }
    
            return maxCount;
        }
    };

Log in to reply
 

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