/**
* Time complexity :
* Space complexity :
*/
class Solution {
public int maxPoints(int[][] points) {
int n = points.length;
if(n <= 1) return n;
Map<String, Integer> slopeMap = new HashMap();
int max = 0;
for(int i = 0; i < n; i++) {
int duplicate = 0;
int tmpMax = 0;
for(int j = i+1; j < n ; j++) {
int dx = points[j][0] - points[i][0];
int dy = points[j][1] - points[i][1];
if(dx == 0 && dy == 0) {
duplicate++;
} else {
String slope = getSlopeKey(dx, dy);
slopeMap.put(slope, slopeMap.getOrDefault(slope, 0)+1);
tmpMax = Math.max(tmpMax, slopeMap.get(slope));
}
}
max = Math.max(max, tmpMax+duplicate+1);
slopeMap.clear();
}
return max;
}
private String getSlopeKey(int dx, int dy) {
if(dx == 0) return "0-1";
if(dy == 0) return "1-0";
int d = gcd(dx, dy);
return (dx/d) + "-" + (dy/d);
}
private int gcd(int a, int b) {
if(b == 0) return a;
return gcd(b, a%b);
}
}
