Max Points on a Line
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
https://leetcode.com/problems/max-points-on-a-line/
Solution:
public class Solution {
public int maxPoints(Point[] points) {
if (points.length == 0) {
return 0;
}
int n = points.length;
int max = 0;
Map<Double, Integer> map = new HashMap<>();
for (int i = 0; i < n; i++) {
int duplicate = 1, vertical = 0; // note that duplicate is initially 1
for (int j = i+1; j < n; j++) {
Point a = points[i];
Point b = points[j];
if (a.x == b.x) {
if (a.y == b.y) {
duplicate++;
} else {
vertical++;
}
} else {
double slope = getSlope(a, b);
if (!map.containsKey(slope)) {
map.put(slope, 1);
} else {
map.put(slope, map.get(slope) + 1);
}
}
}
for (Integer count : map.values()) {
max = Math.max(max, count+duplicate);
}
max = Math.max(max, vertical+duplicate);
map.clear();
}
return max;
}
public double getSlope(Point a, Point b) {
if (a.y == b.y) {
return 0.0;
} // this is necessary
return 1.0 * (a.y - b.y) / (a.x - b.x);
}
}