leetcode Question: Max Points on a Line

Max Points on a Line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Analysis:

First of all, how to know the points are on the same line?  The slope!
The slope of a line can be computed using any two points (x1,y1) (x2,y2) on the line:
 slop = (y2-y1)/(x2-x1) , x2!=x1.

In this problem, we want to know the max number of points on one line. We can think in this way: for every single point, all the possible lines (slopes) which goes across this point and any other point in the plane can be easily computed. Why? Because at least two points can determine a line, if one point is now fixed, use every other point can get all the lines.  For all these lines, they have the same starting point, so if two lines La--Lb and La--Lc have same slope, points a,b and c are actually on the same line. See figure below:

So, we can have a loop from the 1st point to the last point. Within this loop, we compute the slopes from this point to every other point. Then find the max number of points, which has the same slope. e.g., in the figure above, for point 1 (p1), the slops computed are
S:[s11,s12,s13,s14,s15,s16].
Say, s11 to s16 are six lines connecting p1 and p2,3,4,5,6 respectively. If s1i==s1j, i!=j, then p1, pi and pj are on the same line. The maximum number of points on the same line here in this one iteration is the max number of same slopes in S. Once we have this number in one iteration, the max number of all the iterations is what we want.

The algorithm goes like this:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
for each point i in the plane:
    for each point j in the plane:
          if i!=j,
             Compute and store the slop
    Sort the slop array
    Count how many slops are the same
    Store the max number

Output the max number
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


Note:

(1) The slop is computed using "/", if (x2-x1)==0, there will be an error, but in the 2D plane it is a valid line (vertical line). So, store the vertical line as a specific slope is needed.

(2) Remember to consider the input points have duplicates. In my code, I only consider the duplicates with the starting point in each loop, the slop is not computed then but the number of duplicates are stored instead. Also be careful with all the input points are the same case.

See code for more details.


The complexity of this problem is :   O(n*nlgn).    n is the big loop i, nlgn is the sorting complexity (O(nlgn)>O(n))

Code(C++):

/**
 * Definition for a point.
 * struct Point {
 *     int x;
 *     int y;
 *     Point() : x(0), y(0) {}
 *     Point(int a, int b) : x(a), y(b) {}
 * };
 */
class Solution {
public:
    int maxPoints(vector<Point> &points) {
        int n = points.size(); //number of the points
        if (n<=2){return n;}   
        vector<double> k; //vector to store the slops for one point with all the other points
        int res = 0;
        
        for (int i=0;i<n;i++){ // for each point in the 2d plane
            k.clear();
            int dup = 1; // number of the duplicates with currrent point
            for (int j=0;j<n;j++){ 
                if (i!=j){ // for every other point
                    if (points[i].x-points[j].x==0){ // if the slope is a vertical line
                        if (points[i].y-points[j].y==0){ // if the point j is the same as point i
                            dup++;  
                        }else{
                            k.push_back(99999); //store the vertical line to a specific slope
                        }
                    }else{ // if it is the regular slop between point i and j
                        k.push_back(10000*(points[i].y-points[j].y)/(points[i].x-points[j].x)); // store the slope
                    }
                }
            }
            
            sort(k.begin(),k.end()); //sort the slopes for counting
            
            int pp = 1; //number of points in the same line of the point i
            if (k.size()==0){pp=0;} 

            for (int jj=1;jj<k.size();jj++){ //count pp
                if (k[jj]==k[jj-1]){
                    pp++;
                }else{
                    if (pp+dup>res){res=pp+dup;} // res = pp + the number of duplicates
                    pp = 1;
                }
            }
            if (pp+dup>res){res = pp+dup;}
        }

        return res;
    }
};

Code(Python):

# Definition for a point
# class Point:
#     def __init__(self, a=0, b=0):
#         self.x = a
#         self.y = b

class Solution:
    # @param points, a list of Points
    # @return an integer
    def maxPoints(self, points):
        if (len(points)<=2):
            return len(points)
        m = 0 #result value
        for i in range(0, len(points)):
            l = {}  #every time reset the dict
            dup = 1 #count the duplicates
            for j in range(0, len(points)):
                if (points[i].x==points[j].x and points[i].y==points[j].y and i!=j):        
                    dup+=1  #count duplicates
                elif i!=j :
                    if (points[i].x==points[j].x):  #vertical line
                        l['v'] = l.get('v',0) + 1
                    elif (points[i].y==points[j].y): # horizontal line
                        l['h'] = l.get('h',0) + 1
                    else:   #regular slope
                        slope = 1.0*(points[i].y-points[j].y)/(points[i].x-points[j].x)
                        l[slope] = l.get(slope,0)+1
            if (len(l)>0): 
                m = max(m,max(l.values())+dup)
            else: #if all points are duplicates, l is empty.
                m = max(m,dup)
        return m