LeetCode – Max Points on a Line Solution (Python, Java)

Conceptual steps:

1. For each point on the plane, calculate its slopes to other points. Say point A and B.
   1. slope = (YA – YB) / (XA – XB)
   2. Pay attention to the accuracy of decimal (double is estimated value, be sure to use the accurate primitive type in calculation. (Decimal in python, Double in Java)
2. Group all the slopes by their values. The points with the same slope value are on the same line. (try it yourself)
3. Edge cases needs to be handled:
   1. The total number of points is less than 3. (return len(points))
   2. B is at the same place as A. (increment “dup” to include, it is important to initialize dup = 1 to count the point A in each iteration)
   3. Slope is infinite (XA == XB). Use a special value to track (python math.inf) or a variable to track this case.
4. Update the global optimal value with local optimal.
   1. One potential optimization here is to cache the result of slope(A, B) in memory, and have order-agnostic function to map slope(B, A) to the same result. This saves CPU-intensive compute with the trade-off of memory space.

Python3 solution:

from decimal import Decimal
class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        def getK(x, y, a, b):
            if x == a:
                return math.inf
            if y == b:
                return Decimal(0)
            return Decimal(y - b) / Decimal(x - a)
        
        if not points:
            return 0
        res = 0
        for i in range(len(points)):
            dup = 0
            count = {}
            localMax = 0
            for j in range(len(points)):
                if i == j or (points[i][0] == points[j][0] and \
                    points[i][1] == points[j][1]):
                    dup += 1
                    continue
                k = getK(points[i][0], points[i][1], points[j][0], points[j][1])
                count[k] = 1 if k not in count else count[k] + 1
                localMax = max(localMax, count[k])
            res = max(res, localMax + dup)
        return res

Java solution:

/**
 * 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;
        
        int max = 0;
        for (int i = 0; i < points.length; i++) {
            int dup = 0;
            int vertical = 0;
            int localMax = 0;
            Point pi = points[i];
            HashMap<Double, Integer> count = new HashMap<Double, Integer>();
            for (int j = 0; j < points.length; j++) {
                Point pj = points[j];
                if (i == j || (pi.x == pj.x && pi.y == pj.y)) {
                    dup++;
                } else if (pi.x == pj.x) {
                    vertical++;
                } else {
                    double slope = getK(pi, pj);
                    if (!count.containsKey(slope))
                        count.put(slope, 1);
                    else
                        count.put(slope, count.get(slope) + 1);
                    localMax = Math.max(localMax, count.get(slope));
                }
            }
            max = Math.max(max, Math.max(vertical + dup, localMax + dup));
        }
        return max;
    }