C++ solution using map to store slope


#1

The question is taking overlapping(same) points as separate points.
For people who think hashing with only the slope is wrong because a line is characterized by slope AND a point, we are fixing one point and then calculating the slope from other points. So if there is a line with the same slope, it is already defined that it is passing through the first(fixed) point. We are iterating over all such points and hence O(n^2) solution.

int Solution::maxPoints(vector<int> &x, vector<int> &y) {
    int n = x.size();
    if(n<=2) return n;
    int max_points = 2;
    
    unordered_map<double,int> map;
    
    for(int i=0;i<n;i++){
        int same_points = 0;
        int inf_slope = 0; // verticle points
        int curr_max = 0;
        for(int j=i+1;j<n;j++){
            if(x[i]==x[j] && y[i]==y[j]) same_points++; // avoinding 0/0 case
            else if(x[i]==x[j]){        // avoiding division by 0
                inf_slope++;
                curr_max = max(curr_max,inf_slope);
            }else{
                double slope = (y[j]-y[i])/((x[j]-x[i])*1.0);
                map[slope]++;
                curr_max = max(curr_max,map[slope]);
            }
        }
        max_points = max(max_points,curr_max + same_points + 1);
        map.clear();
    }
    
    return max_points;
}


#2

3 4 -4 8 -4 -4 -4 failing in this testcase


#3

@pulkitsharma_ed14a31 I think it is not failing. It gives the correct output i.e. 3


#4

@nikhilp99, I did not understand one thing. When we are fixing one point and calculating a slope to find out the maximum count of the points fall into a particular slope and updating accordingly. Suppose, we are fixing the second point and calculating for other points. But, for the second point, why are we not taking the first point as other point?

For example: (1, 1), (2, 2), (3, 4)
When we are fixing (2,2), then we are not taking (1, 1) as consideration. Why is that? Can you please elaborate?