LeetCode: 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.

---

We can have statistic about the slopes of the line made by each two lines and then we can know which line contains most points. Pay attention to the duplicate points and vertical lines.

C++ Code:

/*
 * func: max_points
 * goal: find the maximum number of points on the same line
 * @param points: a vector of points
 * return: maximum number
 */
/*
 * use a map to store the slop info and find the maximum number
 * complexity: time O(n^2), space O(n)
 */
int max_points(vector<Point> &points){
    size_t size = points.size();
    if(size <= 2){
        return size;
    }
    unordered_map<int, int> slopes;
    int result = 0;
    
    for(int i = 0; i < size; ++i){
        slopes.clear();
        int duplicate = 1;
        int vertical = 0;
        int max_p = 0;
        for(int j = 0; j < size; ++j){
            if(i != j){
                //If it is a vertical line
                if(points[i].x == points[j].x){
                    //If it is a duplicate point
                    if(points[i].y == points[j].y){
                        ++duplicate;
                    }else{
                        max_p = max(max_p, ++vertical);
                    }
                }else{
                    int slope = static_cast<int>(1000000 * (points[i].y - points[j].y) / (points[i].x - points[j].x));
                    max_p = max(max_p, ++slopes[slope]);
                }
            }
        }
        result = max(result, max_p + duplicate);
    }
    return result;
}

Python Code:

# func: find the number of maximum points on the same line
# @param points: list of points
# @return: the maximum number of points
# complexity: time O(n^2), space O(n)
def max_points(points):
    size = len(points)
    if size <= 2:
        return size
    result = 0
    for i in xrange(size):
        slopes = {}
        duplicate = 1
        max_p = 0
        vertical = 0
        for j in xrange(size):
            if i != j:
                #For vertical lines
                if points[i].x == points[j].x:
                    if points[i].y == points[j].y:
                        duplicate += 1
                    else:
                        vertical += 1
                        max_p = max(max_p, vertical)
                else:
                    slope = (int) (1000000 * ((float)(points[i].y - points[j].y) / (points[i].x - points[j].x)))
                    if slope in slopes:
                        slopes[slope] += 1
                    else:
                        slopes[slope] = 1
                    max_p = max(max_p, slopes[slope])

        result = max(result, max_p + duplicate)
    return result