ACCEPTED: A very simple O(N2) solution


  • 0
    L

    Logic : Finding maximum points with similar slopes with all NC2 pairs taken into consideration

    class Solution {
    public:
        int getmax(vector<Point> arr)  // counts similar slope of all n-1 points with respect to arr[0]  :
        {
          map<float,int> mp;
          float m,dy,dx;
          int extra;                  // Takes care of duplicate points
           int max=0;
           extra=1;      
          for(int i=1 ; i<arr.size() ; i++)
          {
              dy=arr[i].y-arr[0].y;
              dx=arr[i].x-arr[0].x;
             if(dx==0 && dy==0)
                 extra++;
             else
             {
              m=(dx!=0)?(dy/dx):(float)INT_MAX;
              mp[m]++;
             }
                
          }
         
          map<float,int> ::iterator i;
          
          for(i=mp.begin() ; i!=mp.end() ; i++)
             if(i->second>max)
               max=i->second;
          
          return max+extra;
            
        }
        
        int maxPoints(vector<Point> &points) {
            int n=points.size();
        
            if(n<=2)
             return n; 
            
            int max,temp_max;
            Point temp;
            max=2;
            for(int i=0 ; i<n; i++)
            {
                temp=points[0];       // Swapping takes care of all NC2 points being examined
                points[0]=points[i];
                points[i]=temp;
                
                temp_max=getmax(points);
                if(temp_max>max)
                 max=temp_max;
            }
            
            return max;
            
        }
    };

  • 0
    L
    This post is deleted!

Log in to reply
 

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