C++ O(N^2) solution


  • 0
    E

    Basically I calculate the equation of every line from the given points.(y = m + b). Then I can compare the equations to see if any points fall on the same line. How I handle duplicates is to first go through the input and remove all duplicate values and record the count in a hashtable. One issue i ran into using Float to calculate slope is if to values are very close to 0 (+-.0005) they will have different slopes. So I do some small rounding around 0 to handle this case. Curious what other think of this solution. I left plenty of comments in the code.

    #include <unordered_map>
    #include <vector>
    #include <string>
    
    using namespace std;
    class Solution {
    public:
    int maxPoints(vector<Point> &points) {
        if(points.size() <= 2) //size is less then or equal to 2 then just return size
            return points.size();
            
        unordered_map<string, int> dupMap;
        for(int i = 0; i < points.size(); i++){ // delete dubs and keep track of their count in dupMap
            string pt = to_string(points[i].x) + ' '+ to_string(points[i].y);
            if(dupMap.count(pt) == 0)
                dupMap[pt] = 0;
            else{
                dupMap[pt]++;
                points.erase(points.begin() + i--);
            }
        }
        
        
        if(points.size() == 1){ //if every item  was a dup
            string pt = to_string(points[0].x) + ' '+ to_string(points[0].y);
            return dupMap[pt] + 1;
        }
        
        int max = 2;
        for(int i = 0; i < points.size()-1; i++){//O(N^2) calclate every combination of points
            unordered_map<string, int> hashMap;
            string pt = to_string(points[i].x) +' '+ to_string(points[i].y);
            
            for(int j = i+1; j < points.size(); j++){
                string pt2 = to_string(points[j].x) +' '+ to_string(points[j].y);
                string eq = "";
                if(points[i].x == points[j].x)
                    eq = "x = " + to_string(points[i].x); //infinte slope
                else{
                    float m = (float)(points[j].y - points[i].y) / (float)(points[j].x - points[i].x);//slope
                    m = (m < 0.0005 && m > -0.0005)? 0: m; //rounding to 0 for floats
                    float b = (float)points[i].y - (float)(m * points[i].x);
                    eq = "y =" + to_string(m) + '+' + to_string(b); //form equation string
                }
                
                if(hashMap.count(eq) == 0){ //havent seen this eq before
                    hashMap[eq] = 2;
                    if(dupMap[pt] > 0) //pt has dupes
                        hashMap[eq] += dupMap[pt];
                    if(dupMap[pt2] > 0)//pt2 has dupes
                        hashMap[eq] += dupMap[pt2];
                }
                else
                    hashMap[eq] += (dupMap[pt2] > 0)? dupMap[pt2] + 1 : 1;
                max = (hashMap[eq] > max)? hashMap[eq] : max;
            }
        }
        return max; //return the max count
    }
    

    };


  • 4
    C

    1 About duplicate.
    I use a new structure newPoint which contains x,y,n. and n is the number of duplication.

    2 About the float slot.
    I have a good idea. Using integer only! **
    Firstly define int variable "up" and "down". up <- pt2.y-pt1.y; down <- pt2.x-pt1.x;
    then we know that slop rate k should be up/down.
    Thus if we want to judge if k1 equals k2,
    we only need to compare
    if( k1.up
    k2.down == k2.up
    k1.down) is true then we know k1 equals k2;
    Since all operation are only multiplication and plus on integers. it's fast and robust.

    the rest are same


  • 0
    L

    ACCEPTED:
    A very simple O(N2) solution

    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
    T

    Nice algorithm!

    A minor suggestion. The running time of your implementation could be cut into half, by enumerating only n (n - 1) / 2 pairs, rather than n * (n - 1).

    For example. Suppose p1, p2, p3 are locating in the optimal line. Your first loop could enumerate some boundary point in this line and get the optimal result, namely three points, regardless of any order of p1, p2, p3 given in advance.


Log in to reply
 

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