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.

First, I thinked out an o(n^3) force solution. It’s workable at last.

However, an o(n^2) solution exists which uses a hash table to store the slope of all lines go through a point.

O(n^3) solution.

1. sort the points by its coordinates o(nlogn)

2. test all possible points. o(n^3)

//o(n^3) solution
//dx, dy, x1, y1
//(y2 - y1) * dx ==? dy * (x2 - x1)
//will the coordinate be very large? say 2^32?
//Some points are equal.(share same location)

//1. sort points by their x coordinates
//2. count duplicate points 

/**
 * 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) {
        //extreme case
        if(points.size() <= 2) return points.size();
        bool isDuplicate = false;
        int max = 0;
        int thisMax = 0;
        //sort the points by their x coordinate
        //sort using a lambda expression 
        sort(points.begin(), points.end(), [](Point a, Point b){
            //bug appeared here
            //in first edition
            //I only compared a.x and b.x while ignored a.y and b.y
            if(a.x < b.x)
                return true;
            else if(a.x > b.x)
                return false;
            else{
                //a.x == b.x
                if(a.y < b.y)
                    return true;
                else
                    return false;
            }
            });
        
        for(auto it1 = points.begin(); it1 != points.end() - 1; it1++){//To be improved end() - max
            int dx = (*(it1 + 1)).x - (*it1).x;
            int dy = (*(it1 + 1)).y - (*it1).y;
            if(dx == 0 && dy == 0){
                //duplicate points
                thisMax++;
            }
            else{
                //not duplicate point
                thisMax++;
                for(auto it2 = it1 + 1; it2 != points.end(); it2++){
                    int curThisMax = thisMax + 1;
                    for(auto it3 = it2 + 1; it3 != points.end(); it3++){
                        if(((*it3).y - (*it1).y) * ((*it2).x - (*it1).x) == ((*it2).y - (*it1).y) * ((*it3).x - (*it1).x)){
                            //on a same line
                            curThisMax++;
                        } 
                    }
                    max = curThisMax > max? curThisMax: max;
                }
                max = thisMax > max? thisMax: max;
                thisMax = 0;
            }
        }
        max = thisMax + 1 > max? thisMax + 1: max;
        return max;
    }
};

o(n^2) solution

slopeMap stores the slope

//
/**
 * 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) {
        if(points.size() <= 2) return points.size();
        //there is a subtle bug here. 
        //Accuracy problem.
        //What the slop of two lines are very closed but not the same?
        unordered_map<double, int> slopeMap;
        int maxRe = 0;
        for(auto it1 = points.begin(); it1!= points.end(); it1++){
            int x = (*it1).x;
            int y = (*it1).y;
            int duplicateNum = 1;
            int nullSlopeNum = 0;
            slopeMap.clear();
            for(auto it2 = it1 + 1; it2 != points.end(); it2++){
                int nx = (*it2).x;
                int ny = (*it2).y;
                //duplicate point
                if(nx == x && ny == y){
                    duplicateNum++;    
                }
                //slop do not exist
                else if(nx == x){
                    nullSlopeNum++;
                }
                //ordinary point
                else{
                    double slope = (double)(ny - y) / (nx - x); //type conversion is important!
                    if(slopeMap.find(slope) == slopeMap.end()){
                        slopeMap[slope] = 1;
                    }
                    else{
                        slopeMap[slope]++;
                    }
                }
            }
            int thisMax = 0;
            for(auto it = slopeMap.begin(); it != slopeMap.end(); it++){
                thisMax = thisMax < it->second? it->second: thisMax;
            }
            maxRe = max(maxRe, nullSlopeNum + duplicateNum);
            maxRe = max(maxRe, thisMax + duplicateNum);
        }
        return maxRe;
        
    }
};