Leetcode 149. Max Points on a Line

Description:

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

Thinking:

if we have three points:(x1,y1), (x2,y2), (x3,y3). If(y1-y2)/(x1-x2) == (y1-y3)/(x1-x3). We can say that this three points are in a line. But using slope as key directly may cause some problems since the precision of Double. Since y0/x0=(y3-y1)/(x3-x1)=(y2-y1)/(x2-x1) So we can use y0 and x0 to track a line.

Complexity:

The time complexity is O(n2).

Steps:

check whether input is valid
create a generateGCD function which is to find the greatest common divisor and simplify x and y.

use a string"x/y" as a key to count localmax points ion a line, the get the max points on a line.

Code:

public class Solution {
 public int maxPoints(Point[] points) {
     if(points == null) return 0;
     int result = 0;
     if(points.length <= 2) return points.length;
     for(int i = 0; i < points.length; i++){
         Map<String, Integer> map = new HashMap<>();
         int samepoint = 0;
         int localmax = 0;
         int count = 0;
         for(int j = i+1; j < points.length; j++){
             int x = points[i].x - points[j].x;
             int y = points[i].y - points[j].y;
             if(x == 0 && y == 0){
                 samepoint++;
                 continue;
             }
             int gcd = generateGCD(x, y);
             x = x/gcd;
             y = y/gcd;
             String slope = x + "/" + y;
             if(map.containsKey(slope)){
                 count = map.get(slope)+1;
                 map.put(slope,count);
             }
             else{
                 count = 1;
                 map.put(slope,count);
             }
             localmax = Math.max(localmax,count);
         }
         result = Math.max(result, localmax + samepoint + 1);
     }
     return result;
 }
 private int generateGCD(int x, int y){
     if(y == 0) return x;
     return generateGCD(y, x%y);
 }
}

Conclusion:

We should consider the condition that the two points are the same. Also, we should notice that the same slope doesn't mean that those points are all on a line. So we should count the localmax in each loop.

Leetcode 149. Max Points on a Line