149. Max Points on a Line

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.

Example 1:

Input: points = [[1,1],[2,2],[3,3]]
Output: 3

Example 2:

Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4

Constraints:

• 1 <= points.length <= 300

• points[i].length == 2

• -104 <= xi, yi <= 104

• All the points are unique.

Solution

My first idea is to calculate the slope base on a point, to the others node. And update the slope count in a map. So we can see how many points are with the same line. And then, we move to next node but ingore the previous node which is done.

public int maxPoints(int[][] points){
    Map<Double, Integer> slopeCount = new HashMap<>();
    int max = 0;
    if(points.length == 0) return max;
    for(int i = 0; i < points.length; i++) {
        int x = points[i][0];
        int y = points[i][1];
        for(int j = i+1; j < points.length; j++) {
            double slope;
            int dy = points[j][1] - y;
            int dx = points[j][0] - x;
            if(dx == 0){
                slope = Integer.MAX_VALUE;
            }else if(dy == 0){
                slope = 0;
            }else{
                slope = (dy*1.0)/dx;
            }
            slopeCount.put(slope, slopeCount.getOrDefault(slope, 0) + 1);
            max = Math.max(max, slopeCount.get(slope));
        }
        slopeCount.clear();
    }
    return max + 1;
}