Super Simple 5ms Java Solution


  • -4
    M
    public class Solution {
    public int maxPoints(Point[] points) {
        if(points.length == 0) return 0;
        if(points.length == 1) return 1;
        
        // check if points have same coordinates
        for(int i=1;i<points.length;i++) {
            Point p1 = points[i-1];
            Point p2 = points[i];
            if(!isEqual(p1,p2)) {
                break;
            } else if(i == points.length - 1) {
                // here we know that no two points
                // are unequal (otherwise, we would
                // not have reached the end of the loop)
                return points.length;
            }
        }
        
        // actual points-on-line test
        int max = 0;
        for(int i=1;i<points.length;i++) {
            Point p1 = points[i-1];
            Point p2 = points[i];
            
            if(!isEqual(p1,p2)) {
                // since p1 != p2, whe know that they
                // represent a line, so we can start with 2
                int n = 2;
                for(Point p3: points) {
                    if(p3 != p1 && p3 != p2 && areOnSameLine(p1,p2,p3)) {
                        n++;
                    }
                }
                if(n > max) {
                    max = n;
                }
            }
        }
        return max;
    }
    
    private boolean isEqual(Point p1, Point p2) {
        return p1 == p2 || (p1.x == p2.x && p1.y == p2.y);
    }
    
    private boolean areOnSameLine(Point p1, Point p2, Point p3) {
        return (p1.y - p2.y) * (p1.x - p3.x) == (p1.y - p3.y) * (p1.x - p2.x);
    }
    }

  • 1
    S

    What if the points on the line consisting of most of the points are all not adjacent in the original list of points?


  • 0
    Y

    SimbaTien is correct, this code is wrong. It got AC because of lack of test cases. For example it will return 2 with this input: [[0, 0], [432, 2532], [1, 0], [23, 342], [2, 0]].
    The code could be easily corrected though, but then it won't be 5ms.


Log in to reply
 

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