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

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

• try [[0,0],[3,5],[2,2],[4,30],[6,6]]

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