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.

Solution:
1)one line can be determined by two factors. y = slope * x + intercept. intercept is point which is intercepted by X line and this line.
In this code, we use the i point (the start of the outer loop) instead of intercept.
since for all j points, the reference point is i point. like sun light, i point is the start point of all the sun light for inner looper. for parallel, two lines have two start point. for each start point, the max variable and overlap variable is to caculate the max point numbers in one line, need to reassign to 0. map is also only for this line, need to clear for each start point. 
2) how to get slope.
double slope = differY/differX. because double is close when differY,differX is very large. so can't use double. it's determined by differY and differX. so these two factors could be the key of the map.

    //y = x * slope + interept; -> y = x * slope + i point (as start point of the line);

    public int maxPoints(int[][] points) {
        HashMap<String,Integer> map = new HashMap<String,Integer>();
        int res = 0;
        for(int i = 0; i < points.length; i++){
            map.clear();//is new for each time of the outer loop
            int overlap = 0;
            int max = 0;
            for(int j = i + 1; j <points.length; j++){
             if(points[j][1] == points[i][1] && points[j][0] == points[i][0]) {
              overlap++;
              continue;
             }
                int differY = points[j][1] - points[i][1];
                int differX = points[j][0] - points[i][0];
                int gcd = gcd(differX,differY);
                String key = (differX/gcd)+"@"+(differY/gcd);
                Integer count = map.get(key);
                Integer value = count != null ? count+1:1;
                map.put(key,value);
                max = Math.max(value,max);
            }
            res = Math.max(res, max+overlap+1);
                          
        }
        return res;
    }
    
    public int gcd(int a, int b) {
     if(b == 0) return a;
     return gcd(b,a%b);
    }