C++ easy to understand solution


  • 0

    In linear algebra, two different points defines a line, y = ax + b, to be more general to consider vertical line which can be represented using x = c, I use the following representation for line: by = ax + c.

    Map stats is created to record the straight lines with count of points on it. For easy understanding, I converted by = ax + c into a string as map's key value: "by=ax+c", e.g. "2y=3x+0", and its value is number of points on that line accordingly.

    However, how about two points that are the same? It's valid for the test cases, so I decided to preprocess the points using a frequency map, let it be freq to store the unique points with frequency.

    Then iterate through map freq, outer loop pointer it1 starts from the 2nd point till the last point, the inner loop pointer it2 is basically iterating through each point before it1 in freq. If it1 and it2 defines a line that already exists in stats, simply add count of it1 in freq map to line; Otherwise, it1 and it2 identifies a new line, update the stats map accordingly. One thing to note, in the inner loop, (it1, it2) and (it1, it2') may actually define the same line, so as to avoid adding the count of it1 to the same line more than once, I use a set visit to record lines that have already counted it1, and visit needs to be reset for each outer loop pointer it1.

    class Solution {
    public:
        int maxPoints(vector<Point>& points) {
            if(points.size() <= 2) return (int)points.size();
            unordered_map<string, int> stats;
            map<pair<int, int>, int> freq;
            unordered_set<string> visited; 
            
            for(auto p: points){
                freq[make_pair(p.x, p.y)]++;
            }
            
            int ans = freq.begin()->second;
            for(auto it1 = ++freq.begin(); it1 != freq.end(); ++it1){
                visited.clear();
                for(auto it2 = freq.begin(); it2 != it1; ++it2){
                    int deltaX = it1->first.first - it2->first.first;
                    int deltaY = it1->first.second - it2->first.second;
                    int d = gcd(deltaX, deltaY);
                    int a = d ? deltaY / d : 1;
                    int b = d ? deltaX / d : 0;
                    int c = b * (it1->first.second) - a * (it1->first.first);
                    
                    string line = to_string(b) + "y=" + to_string(a) + "x+" + to_string(c);
                    if(stats.find(line) == stats.end()){
                        stats[line] = it1->second + it2->second;
                        visited.insert(line);
                    }else {
                        if(visited.find(line) == visited.end()){
                            stats[line] += it1->second;
                            visited.insert(line);
                        }
                    }
                    ans = max(ans, stats[line]);
                }
            }
            
            return ans;
        }
        
        int gcd(int a, int b) {
            return b == 0 ? a : gcd(b, a % b);
        }
    };

Log in to reply
 

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