# Java O(n^2) Solution

• Java O(n^2) Solution.

O(n^2) enumrate every point and use a HashMap to save the slope of this points between the other points.

All points in the same line share same slope.

Slope can be represent by a Pair (dur_of_x / gcd , dur_of_y / gcd) to avoid double which may cause compute precision error.

Be careful of the points with the same position.

``````import java.util.*;
import javafx.util.Pair;

public class Solution {

int n;
int cnt = 0;
Map<Pair<Integer,Integer>,Integer> mp ;
List<Set<Integer>> lst;

int gcd(int a,int b) {
if(a==0) return b;
return gcd(b%a,a);
}

public int maxPoints(Point[] points) {

n = points.length;
if(n==0) return 0;
int mx=1;

for(int i=0;i<n;i++) {

mp = new HashMap<>();
lst = new ArrayList<>();
cnt = 0;
int same = 0;

for(int j=0;j<n;j++) {

if(i==j) continue;

int dx = points[i].x - points[j].x;
int dy = points[i].y - points[j].y;

if(dx==0&&dy==0) {
same ++;
continue;
}

int ddx = dx;
if(ddx<0) ddx=-ddx;
int ddy = dy;
if(ddy<0) ddy=-ddy;

int g = this.gcd(ddx, ddy);

dx = dx/g;
dy = dy/g;

if(dx<0&&dy<0) {
dx *= -1;
dy *= -1;
}
if(dx>0&&dy<0) {
dx *= -1;
dy *= -1;
}

int listid = mp.getOrDefault(new Pair(dx,dy),-1);

if(listid==-1) {
mp.put(new Pair(dx,dy),cnt);
listid = cnt;
cnt++;
}

}

for(Pair<Integer,Integer> key : mp.keySet()) {
int listid = mp.get(key);
int inoneline = lst.get(listid).size();
if(mx<inoneline+same) {
mx = inoneline+same;
}
}
if(mx<same+1) {
mx = same+1;
}
}

return mx;
}
}
``````

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