My Java AC code. Easy to understand


  • 0
    T

    First sort all points with x ascending and y ascending. For each point, find who's on the same point. Every line through this point will go through all the points on the same spot. Then find who's on the vertical line as the slope is infinite. Then find other lines. Skip the same point while in the outer iteration.

    public class Solution {
        public int maxPoints(Point[] points) {
            Arrays.sort(points, new Comparator<Point>() {
                @Override
                public int compare(Point p1, Point p2) {
                    return p1.x - p2.x == 0 ? p1.y - p2.y : p1.x - p2.x;
                }
            });
            int max = 0;
            int samePoint = 0;
            double k = 0;
            Map<Double, Integer> map = new HashMap<>();
            for (int i = 0; i < points.length; i++) {
                Point p1 = points[i];
                samePoint = 1;
                max = Math.max(max, samePoint);
                map.clear();
                for (int j = i+1; j < points.length; j++) {
                    Point p2 = points[j];
                    if (p2.x == p1.x && p2.y == p1.y) {
                        samePoint++;
                        max = Math.max(max, samePoint);
                    } else if (p2.x == p1.x) {
                        k = Double.MAX_VALUE;
                        map.put(k, map.containsKey(k) ? map.get(k)+1 : samePoint+1);
                        max = Math.max(max, map.get(k));
                    } else {
                        k = (double)(p2.y - p1.y) / (p2.x - p1.x);
                        map.put(k, map.containsKey(k) ? map.get(k)+1 : samePoint+1);
                        max = Math.max(max, map.get(k));
                    }
                    while (i+1 < points.length && points[i+1].x == points[i].x && points[i+1].y == points[i].y) {
                        i++;
                    }
                }
            }
            return max;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.