Concise and easy to understand O(n^2) c++ solution

interview-questions
Tags: #<Tag:0x00007f24270364c8>

#1

We have to calculate 2 values for each point p:

1. overlapCount : Count of points same as the current point p (overlapping points).
2. maxGroupSize : The number of points in each group of points sharing the same slope with the current point p. We want to find out the size of the biggest group among all.
For calculating this we can maintain a hash map which will map each unique value of slope to the count of points having that slope with current point p( unordered_map < slope, count_of_points > ).


The maximum value of overlapCount + maxGroupSize among all the given points will be our answer.

int Solution::maxPoints(vector<int> &A, vector<int> &B) {
    int maxCount = 0;
    for(int i=0;i<A.size();i++){
        int maxGroupSize = 0, overlapCount = 1;
        unordered_map<double,int> slopeMap;
        for(int j=i+1;j<A.size();j++){
            if( A[i]==A[j] and B[i]==B[j] )overlapCount++; //finding overlap count
            else{
                double slope = A[i]!=A[j]? (1.0*B[j]-B[i])/(A[j]-A[i]): 1e9;
                maxGroupSize = max( maxGroupSize, ++slopeMap[slope]); // simultaneously calculating the size of the biggest group sharing same slope with ( A[i], B[i] ).
            }
        }
        maxCount = max(maxCount,  overlapCount + maxGroupSize);
    }
    return maxCount;
}


#2

Better than editorial.


#3

Glad you find it helpful.