149. Max Points on a Line

149. Max Points on a Line

Question

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.

Solutions:

• Method 1: I first used the double to calculate the slope but cause precision error. O(n^3) cannot AC.

    class Solution {
        public int maxPoints(int[][] points) {
            int len = points.length;
            if(len <= 2) return len;
            int res = 0;
            for(int i = 0; i < len; i++){
                for(int j = i + 1; j < len; j++){
                    int temp = 2;
                    double x1 = (double)points[i][0];
                    double x2 = (double)points[j][0];
                    if(x1 != x2){
                        double y1 = (double)points[i][1];
                        double y2 = (double)points[j][1];
                        double s = (y2 - y1) / (x2 - x1);
                        double b = y1 - s * x1;
                        for(int k = 0; k < len; k++){
                            if(k == i || k == j) continue;
                            double x = (double)points[k][0];
                            double y = (double)points[k][1];
                            if(y == x * s + b) temp++;
                        }
                    }else{
                        for(int k = 0; k < len; k++){
                            if(k == i || k == j) continue;
                            double x = (double)points[k][0];
                            if(x == x1) temp++;
                        }
                    }
                    res = Math.max(res, temp);
                }
            }
            return res;
        }
    }
  

• Method 2: HashMap to save the slope(use string) AC

    class Solution {
        public int maxPoints(int[][] points) {
            int len = points.length;
            if(len <= 2) return len;
            int res = 0;
            for(int i = 0; i < len; i++){
                for(int j = i + 1; j < len; j++){
                    int temp = 2;
                    double x1 = (double)points[i][0];
                    double x2 = (double)points[j][0];
                    if(x1 != x2){
                        double y1 = (double)points[i][1];
                        double y2 = (double)points[j][1];
                        double s = (y2 - y1) / (x2 - x1);
                        double b = y1 - s * x1;
                        for(int k = 0; k < len; k++){
                            if(k == i || k == j) continue;
                            double x = (double)points[k][0];
                            double y = (double)points[k][1];
                            if(y == x * s + b) temp++;
                        }
                    }else{
                        for(int k = 0; k < len; k++){
                            if(k == i || k == j) continue;
                            double x = (double)points[k][0];
                            if(x == x1) temp++;
                        }
                    }
                    res = Math.max(res, temp);
                }
            }
            return res;
        }
    }