LeetCode [149] Max Points on a Line

149. Max Points on a Line

Hard

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

Example 1:

Input: [[1,1],[2,2],[3,3]]
Output: 3
Explanation:
^
|
|        o
|     o
|  o  
+------------->
0  1  2  3  4

Example 2:

Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation:
^
|
|  o
|     o        o
|        o
|  o        o
+------------------->
0  1  2  3  4  5  6

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

//C++: method1 53ms
/**
 * 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 {
    int gcd(int a, int b){
        return a?gcd(b%a, a):b;
    }
public:
    int maxPoints(vector<Point> &points) {
        int res=0;
        int n = points.size();
        for(int i=0; i<n; ++i){
            unordered_map<string, int> lc;
            int same = 1;
            int maxLines = 0;
            for(int j=i+1; j<n; ++j){
                int x = points[i].x-points[j].x;
                int y = points[i].y-points[j].y;
                int d = gcd(x,y);
                if(d==0){
                    same++;
                }else{
                    x/=d; 
                    y/=d;
                    string slope = to_string(x)+" "+to_string(y);
                    lc[slope]++;
                    maxLines = max(maxLines, lc[slope]);
                }
            }
            res = max(res, same+maxLines);
        }
        return res;
    }
};

//Java
class Solution {
    int gcd(int a, int b){
        return a==0 ? b : gcd(b%a, a);
    }
    public int maxPoints(int[][] points) {
        int n = points.length;
        int ret = 0;
        for(int i=0; i<n; ++i){
            Map<String, Integer> map = new HashMap<>();
            int pointsOverlapWithI = 1;//including point i
            int maxPointsWithSameSlopeCrossingI = 0;//not including point i
            for(int j=i+1; j<n; ++j){
                int dx = points[i][0]-points[j][0];
                int dy = points[i][1]-points[j][1];
                int d = gcd(dx, dy);
                if(d==0){
                    pointsOverlapWithI++;
                }else{
                    dx /= d;
                    dy /= d;
                    String sl = dx + ":" + dy;
                    map.put(sl, map.getOrDefault(sl, 0)+1);
                    maxPointsWithSameSlopeCrossingI = Math.max(maxPointsWithSameSlopeCrossingI, map.get(sl));
                }
            }
            ret = Math.max(ret, maxPointsWithSameSlopeCrossingI + pointsOverlapWithI);
        }
        return ret;
    }
}