Max Points on a Line | Leetcode

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

---

Solution: For each pair of points (O(N²)), first check whether they are the same point or not. If not, calculate the slope of the line passing through both of them. Keep count of the number of times each slope appears. The number of points on the same line for point X is the total of points which are identical to X (including point X itself) plus the maximum number of points having the same slope with a line passing through X. Since all these lines will pass through X, having the same slope will mean that they are the same line.

Keep track of the maximum count for each point of origin X and return the maximum count among all points as the answer.

/**
 * 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.length == 0) return 0;
        
        // At least one point will be on the same line as itself.
        int max = 1;
        
        // Using Double as the key is not ideal for double equality comparison,
        // but it works well enough to pass the Leetcode submission.
        // If we want to use approximate double comparison, we can use a loop
        // in the slope lookup logic to find a matching slope if it exists.
        Map<Double, Integer> slopeCount = new HashMap<>();
        
        for (int i = points.length - 1; i >= 1; i--) {
            int x1 = points[i].x;
            int y1 = points[i].y;
            
            int sameCount = 1; // add points[i] itself
            int verticalCount = 0;
            int horizontalCount = 0;
            int thisSlopeMax = 0;
            
            for (int j = i - 1; j >= 0; j--) {
                int x2 = points[j].x;
                int y2 = points[j].y;
                
                if (x1 == x2 && y1 == y2) {
                    sameCount++;
                } else if (x1 == x2) {
                    verticalCount++;
                } else if (y1 == y2) {
                    // By right not needed, but Java will consider 0.0 != -0.0,
                    // hence it is safer to just avoid this problem altogether.
                    horizontalCount++;
                } else {
                    double slope = ((double) (y1 - y2)) / ((double) (x1 - x2));
                    Integer oldSlopeCount = slopeCount.get(slope);
                    int newSlopeCount = (oldSlopeCount == null) ? 1 : oldSlopeCount + 1;
                    slopeCount.put(slope, newSlopeCount);
                    
                    thisSlopeMax = Math.max(thisSlopeMax, newSlopeCount);
                }
            }
            
            thisSlopeMax = Math.max(thisSlopeMax, Math.max(verticalCount, horizontalCount));
            max = Math.max(max, sameCount + thisSlopeMax);
            
            slopeCount.clear();
        }
        
        return max;
    }
}