9ms No HashMap 3 Points Java Solution (beats 99.88 % of java submission)


  • 0
    L

    The main idea is getting a line by two adjacent points: "P[i] -- P[i - 1]". Then find how many other points stay on the same line.

    A corner case is how to avoid the 3rd points on a parallel line.
    Since the slop is calculated from p1 and p2. It means lines p0--p1 and p1--p2 intersect with the point p1. Once their slopes are equal, then p2 should be on the line of p0--p1.

    Time : O(n^2)
    Space: O(1)

        public int maxPoints(Point[] points) {
            if (points == null) {
                return 0;
            } else if (points.length < 3) {
                return points.length;
            }
    
            int max = 0;
            Point p0, p1, p2;
            for (int i = 1; i < points.length; i++) {
                //Find a line based on p0 and p1
                p0 = points[i - 1];
                p1 = points[i];
                double k = getSlop(p0, p1);
                //Count how many other points on the same line
                int count = 2;  //2 points already
                for (int j = 0; j < points.length; j++) {
                    if (j == i || j == i - 1) {
                        continue; //the 3rd point should not be the p0 or p1
                    }
                    p2 = points[j];
                    if (k == Double.POSITIVE_INFINITY && p1.x == p2.x) {
                        //Check on the same vertical line
                        count++;
                    } else if (isOverlap(p1, p2) || isOverlap(p0, p2)) {
                        //Check for the overlap with the 2 endpoints of the line
                        count++;
                    } else {
                        //Check for the same slop
                        if (k == getSlop(p1, p2)) {
                            count++;
                        }
                    }
                }
                //Update max for the points on line y = kx + b
                max = Math.max(max, count);
            }
            return max;
        }
    
        private boolean isOverlap(Point p1, Point p2) {
            return p1.x == p2.x && p1.y == p2.y;
        }
    
        private double getSlop(Point p1, Point p2) {
            if (p2.x == p1.x) {
                return Double.POSITIVE_INFINITY;
            } else {
                return (double) (p2.y - p1.y) / (p2.x - p1.x);
            }
        }
    

  • 0
    K

    try [[0,0],[3,5],[2,2],[4,30],[6,6]]
    your code returns 2, but the expected answer should be 3.


Log in to reply
 

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