149. Max Points on a Line(# 1).java

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
class Solution {
    public int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    public int maxPoints(Point[] points) {
        if (points == null || points.length < 1) return 0;
        int len = points.length;
        if (len <= 2) return len;
        int res = 2;
        for (int i = 0; i < len; i++) {
            if (res >= len - i) return res; // if the number of the left points is less than res
            Map<String, Integer> map = new HashMap<>();
            int sameX = 1;
            int sameP = 0;
            int diff = 0;
            for (int j = i + 1; j < len; j++) {
                if (i != j) {
                    if (points[i].x == points[j].x && points[i].y == points[j].y) {
                        sameP++;
                    } 
                    if (points[i].x == points[j].x) {
                        sameX++;
                        continue;
                    }
                    
                    int a = points[i].x - points[j].x;
                    int b = points[i].y - points[j].y;
                    int gcd = gcd(a,b);
                    String hashStr = (b / gcd) + "_" + (a / gcd);
                    map.put(hashStr, map.getOrDefault(hashStr, 1) + 1);
                    diff = Math.max(diff, map.get(hashStr));
                }
            }
            res = Math.max(res,Math.max(diff + sameP, sameX));
        }
        return res;
    }
}

149. Max Points on a Line.java

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
public class Solution {
    public int maxPoints(Point[] points) {
        if(points == null || points.length == 0) return 0;
        if(points.length <= 2) return points.length;
        int res = 0;
        //HashMap<Double, Integer> map = new HashMap<Double, Integer>(); 
        for(int i = 0; i < points.length; i++){
            HashMap<String, Integer> map = new HashMap<String, Integer>();// each points:storing the different k and frequency
            int sameX = 1;
            int sameP = 0;
            for(int j = 0; j < points.length; j++){
                if(i != j){
                    if(points[i].x == points[j].x && points[i].y == points[j].y ){
                        sameP++;
                    } 
                    if(points[i].x == points[j].x){
                        sameX++;
                        continue;// deal with a zero denominator 
                    } 
                    //double k = (double)(points[j].y - points[i].y) / (double)(points[j].x - points[i].x);
                    //In order to avoid using double type(the slope k) as map key, I used pair (int a, int b) as the key where a=pj.x-pi.x, b=pj.y-pi.y, and k=b/a. Using greatest common divider of a and b to divide both a, b ensures that lines with same slope have the same key.
                    //eg:[[0,0],[94911151,94911150],[94911152,94911151]]
                    
                    int a = points[j].y - points[i].y;
                    int b = points[j].x - points[i].x;
                    int gcd = gcd(a,b);

                    String hashStr = (a/gcd) + "_" + (b/gcd);
                    if(map.containsKey(hashStr)){
                        map.put(hashStr, map.get(hashStr) + 1);
                    } else {
                        map.put(hashStr, 2);
                    }
                    res = Math.max(res, map.get(hashStr) + sameP);
                }
            }
            res = Math.max(res, sameX);
        }
        return res;
    }
    
    public int gcd(int x, int y){
        return (y == 0) ? x : gcd(y, x % y);
        //辗转相除法
        /* 
        60 : 12 12 12 12 12 
        24 : 12 12 
        60 % 24 = 12 找到了最小的一块
        24 % 12 = 0  找完了！
        
        */
    }
    
}

149. Max Points on a Line.py

# Time: O(n^2)
# Space: O(n)
# Max Points on a Line
'''
slope:
1. the same 
2.1 inf
2.2 not inf 

edge case:
python: [[0,0],[94911151,94911150],[94911152,94911151]]

Correct Code means you need to consider edge cases.

- point in points may be duplicate.
- use a*y + b*x + c = 0 to represent a line, not y = k*x + b, because k and b may be float number, and float numbers can't be compared with =. Two equal key in hash table representing line may differ.



'''
from collections import defaultdict 
# Definition for a point.
class Solution(object):
    def __init__(self, a=0, b=0):
        self.x = a
        self.y = b

    def gcb(self, a, b):
        while b:
            a, b = b, a % b
        return a

    def maxPoints(self, points):
        """
        :type points: List[Point]
        :rtype: int
        """
        from collections import defaultdict
        result, lens, points = 0, len(points), map(lambda p: (p.x, p.y), points)                
        for i in range(lens):
            x1, y1 = points[i]
            same, lines = 1, defaultdict(int)
            for j in range(i+1, lens):
                x2, y2 = points[j]
                if x1 == x2 and y1 == y2:
                    same += 1  
                else:
                    # [x1,y1],[x2,y2]
                    # [1,  6],[2, 4 ]
                    # y = kx + m
                    # a = k = (x1-x2)/(y1-y2); b = -1; c = 
                    # c = 
                    # ax + by + c = 0
                    # a = -4 + 6, b = -1 + 2, c = -6*2 + 4*1
                    
                    if y2 < y1 or y2 == y2 and x1 < x2:
                        a, b, c = - y2 + y1, - x1 + x2, - y1 * x2 + y2 * x1
                    else:    
                        a, b, c = y2 - y1, x1 - x2, y1 * x2 - y2 * x1
                    rate = self.gcb(self.gcb(a, b), c)     
                    lines[(a / rate, b / rate, c /rate)] += 1 
            result = max(result, (max(lines.values()) if lines.values() else 0) + same)
        return result    

    

# class Solution(object):
#     def maxPoints(self, points):
#         """
#         :type points: List[Point]
#         :rtype: int
#         """
#         max_points = 0
#         for i, start in enumerate(points):
#             slope_count, same = collections.defaultdict(int), 1
#             for j in xrange(i + 1, len(points)):
#                 end = points[j]
#                 # the same points 
#                 if start.x == end.x and start.y == end.y:
#                     same += 1
#                 else:
                    
#                     # slope is inf 
#                     slope = float("inf")
#                     if start.x - end.x != 0:
#                         # slope is not inf 
#                         slope = (start.y - end.y) * 1.0 / (start.x - end.x)
#                     slope_count[slope] += 1
            
#             current_max = same 
#             for slope in slope_count:
#                 current_max = max(current_max, slope_count[slope] + same)
                        
#             max_points = max(max_points, current_max)
        
#         return max_points