Code review please. 44 ms runtime.


  • 0

    This is my C++ solution (44 ms runtime). I would appreciate if someone could help in reviewing it in terms of complexity and readability. Assume complexity of CRUD operations in map to be O(1) amortized.

    /**
     * Definition for a point.
     * struct Point {
     *     int x;
     *     int y;
     *     Point() : x(0), y(0) {}
     *     Point(int a, int b) : x(a), y(b) {}
     * };
     */
    class Solution {
    public:
        vector<map<double, int>> cache;
        vector<int> dup;
        
        int maxPoints(vector<Point>& points) {
            int n = points.size();
            int maxi = 0, maxidx = 0;
            
            if(n == 0)
                return 0;
                
            cache.resize(n);
            dup.resize(n, 0);
            
            for(int i=0; i<n-1; i++) {
                Point a = points[i];
                for(int j=i+1; j<n; j++) {
                    Point b = points[j];
                    if(a.x == b.x && a.y == b.y) {
                        dup[i]++;
                        dup[j]++;
                    } else {
                        double slope = ((b.x != a.x) ? (double)(b.y - a.y) / (double)(b.x - a.x) : numeric_limits<double>::max());
                        cache[i][slope]++;
                        cache[j][slope]++;
                    }
                }
                
                auto temp = max_element(cache[i].begin(), cache[i].end(), [](const pair<double, int>& p1, const pair<double, int>& p2) {
                    return p1.second < p2.second;
                });
                
                if(temp != cache[i].end()) {
                    maxi = max(maxi, temp->second);
                    maxidx = (maxi == temp->second) ? i : maxidx;
                }
            }
            
            cache.clear();
            dup.clear();
            
            return maxi+dup[maxidx]+1;
        }
    };
    

Log in to reply
 

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