Readable Java solution O(n^2)


  • 0
    D
    public class Solution {
        class Slope {
            int nominator;
            int denominator;
            public boolean isVertical() {
                return denominator == 0;
            }
            public Slope(int nominator, int denominator) {
                if (denominator == 0) {
                    return;
                }
                if (nominator == 0) {
                    this.denominator = 1;
                    return;
                }
                int gcdVal = gcd(Math.abs(nominator), denominator);
                this.nominator = nominator / gcdVal;
                this.denominator = denominator / gcdVal;
            }
            public boolean equals(Object other) {
                if (!(other instanceof Slope)) {
                    return false;
                }
                Slope otherSlope = (Slope)other;
                return (isVertical() && otherSlope.isVertical()) || (nominator == otherSlope.nominator &&
                        denominator == otherSlope.denominator);
            }
            public int hashCode() {
                int hash = 17;
                hash = hash * 31 + nominator;
                hash = hash * 31 + denominator;
                return hash;
            }
            private int gcd(int a, int b) {
                if (b == 0) {
                    return a;
                }
                if (a == b) {
                    return a;
                } else if (a < b) {
                    return gcd(b, a);
                } else {
                    return gcd(a % b, b);
                }
            }
        }
    
        class SlopePoints {
            int samePoints;
            int verticalSlopePoints;
            Map<Slope, Integer> slopePointsMap = new HashMap<>();
        }
    
        public int maxPoints(Point[] points) {
            if (points == null || points.length == 0) {
                return 0;
            }
            int n = points.length;
            if (n == 1) {
                return 1;
            }
            Arrays.sort(points, new Comparator<Point>() {
                @Override
                public int compare(Point point1, Point point2) {
                    return point1.x != point2.x ? point1.x - point2.x : point1.y - point2.y;
                }
            });
            SlopePoints[] slopePointz = new SlopePoints[n];
            for (int i = 0; i < n; i++) {
                slopePointz[i] = new SlopePoints();
                for (int j = i; j < n; j++) {
                    if (points[i].x == points[j].x && points[i].y == points[j].y) {
                        slopePointz[i].samePoints++;
                    } else if (points[i].x == points[j].x) {
                        slopePointz[i].verticalSlopePoints++;
                    } else {
                        Slope slope = new Slope(points[j].y - points[i].y, points[j].x - points[i].x);
                        int origPoints = slopePointz[i].slopePointsMap.containsKey(slope)
                                ? slopePointz[i].slopePointsMap.get(slope) : 0;
                        slopePointz[i].slopePointsMap.put(slope, origPoints + 1);
                    }
                }
            }
            int maxPoints = 0;
            for (SlopePoints slopePoints : slopePointz) {
                maxPoints = Math.max(maxPoints, slopePoints.samePoints + slopePoints.verticalSlopePoints);
                for (int numPoints : slopePoints.slopePointsMap.values()) {
                    maxPoints = Math.max(maxPoints, slopePoints.samePoints + numPoints);
                }
            }
            return maxPoints;
        }
    }

  • 0
    W

    You may ignore that the overhead of "gcd" can't be O(1). If the number of points is rare, but the x and y are large, your algorithm may not be suitable.


Log in to reply
 

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