• ``````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;
}
}``````

• 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.

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