Most Simple Approach O(N*N) using unordered maps!

interview-questions
programming
Tags: #<Tag:0x00007f24288b3078> #<Tag:0x00007f24288b2e48>

#1
int Solution::maxPoints(vector<int> &X, vector<int> &Y) {
// Do not write main() function.
// Do not read input, instead use the arguments to the function.
// Do not print the output, instead return values as specified

// Still have a doubt. Checkout www.interviewbit.com/pages/sample_codes/ for more details
if(X.size()==0)
return 0;

 int overall_max = 0;
 unordered_map<double,int> map;
 int N=X.size();
 for(int i=0;i<N;i++)
 {
 for(int j=0;j<N;j++)
 {
     //fixed point
     if(i!=j)
     {
     int x = X[i];
     int y = Y[i];
     // varying point
     int temp_x = X[j];
     int temp_y = Y[j];
     if((temp_x-x)==0)
     {
         map[INT_MAX]++;
     }
     else
     {
         double slope =  (temp_y-y)/((temp_x-x)*1.0);
         map[slope]++;
     }
     }
 }
  for(auto i:map)
  {
      if(i.second>overall_max)
      overall_max = i.second;
  }
  map.clear();
 }
 return overall_max+1;

}