8ms Java Solution (based on sorting the points first)


  • 0

    We will go through pairs of points, seeing how many points are on line connecting them.

    We can do this intelligently by first sorting our array. That way, we know that any point k that comes between points i and j in our array must also be "between" points i and j on the plane. This means we can go through them in order, starting with the pairs "furthest" apart (this might not be furthest by distance because we only consider y when are x's are the same, but furthest by number of possible points between them).

    We can also keep track of pairs that have been checked so we don't have to recheck them (if a pair has been checked that means we already know the max number of points any line containing those two could have). The solution without the checked array is still very fast (tested at 11ms) and would be O(n) space because Arrays.sort uses merge sort for objects (though it doesn't need to be stable so we could use another sort if we really wanted constant space).

    I am not 100% sure that breaking our j-loop if we checked that i,j pair works for all cases (it does for the test cases). We could definitely bypass the k-loop if it has been checked, but breaking is a bit more tricky. If we don't have that break in our k-loop, the checked[i][j] break does not work (removing checked[i][k] = true will fix this, and we could check that separately to see if we should do the k-loop, which is easy because we're only using the half of the array where row < column, so we could just store that in the other half). I'd have to think a bit more to see if there is something tricky going on that makes breaking in this way work.

    class Solution {
        public int maxPoints(Point[] points) {
            int n = points.length;
            if(n < 3) return n;
            
            Arrays.sort(points, new Comparator<Point>() {
                public int compare(Point a, Point b) {
                    if(a.x == b.x) {
                        return a.y - b.y;
                    }
                    return a.x - b.x;
                }
            });
            
            //time optimization - true when pair has been checked
            //only uses the half where row < column
            boolean[][] checked = new boolean[n][n];
    
            int answer = 2;
            for(int i=0; i<n; i++) {
                if(answer >= n-i) {
                    /*
                        The greatest possible number of points we can have starting at i is n-i.
                        Since it's ordered, we have gone through our greatest possibilites first.
                    */
                    return answer;
                }
                Point a = points[i];
                for(int j=n-1; j>i; j--) {
                    if (j - i + 1 <= answer || checked[i][j]) {
                        /*
                            Once the number of points we can check between i and j is less than
                            our current answer, we won't be able to do any better for this i.
                            We also can break if we checked this combination.
                        */
                        break;
                    } 
                    Point b = points[j];
                    int pointCount = 2;
                    for(int k=i+1; k<j; k++) {
                        //Check how many points on the line between point[i] and point[j]
                        if(pointCount + j - k <= answer) break;
                        if(pointOnLine(a, b, points[k])) {
                            checked[i][k] = true;
                            checked[k][j] = true;
                            pointCount++;
                        }    
                    }
                    answer = Math.max(pointCount, answer);
                }
            }
            return answer;
        }
        private boolean pointOnLine(Point a, Point b, Point check) {
            return (long) (check.x - a.x) * (b.y - check.y) == (long) (b.x - check.x) * (check.y - a.y);
        }
    }
    

Log in to reply
 

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