Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.
/**
* Definition for a point.
* class Point {
* int x;
* int y;
* Point() { x = 0; y = 0; }
* Point(int a, int b) { x = a; y = b; }
* }
*/
class Solution {
public int maxPoints(Point[] points) {
// edge case
if (points == null || points.length == 0) return 0;
if (points.length <= 2) return points.length;
int res = 0;
for (int i = 0; i < points.length; i++) {
HashMap<String, Integer> map = new HashMap<>();
int samePoint = 0;
int sameXAxis = 1;
// 3 scenarios: 1) samepoint; 2) in the same x axis; 3) has same slope
for (int j = 0; j < points.length; j++) {
// if (i == j) continue;
if (i != j) {
// same point
if (points[i].x == points[j].x && points[i].y == points[j].y) samePoint++;
// same x axis
if (points[i].x == points[j].x) {
sameXAxis++;
continue; // cannot calculate slope, continue
}
// slope
int numerator = points[i].y - points[j].y;
int denominator = points[i].x - points[j].x;
int gcd = gcd(numerator, denominator);
String hashStr = (numerator / gcd) + "/" + (denominator / gcd);
map.put(hashStr, map.getOrDefault(hashStr, 1) + 1); // 2 points in same slope
res = Math.max(res, map.get(hashStr) + samePoint);
}
}
res = Math.max(res, sameXAxis);
}
return res;
}
private int gcd(int a, int b) {
if(a == 0) return b;
return gcd(b % a, a);
}
}
