leetcode 149.
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
Solution. A naive idea is that assume we have line formula y = kx + b. Every 2 points can determines a line by (k, b). Then we build a hashmap which has (k, b) as key, and count as value. We iterate every 2 points and count the number of edges belonging to same line. But this count is not the answer. For example, we have 5 points in same line. Each pair of points will meet 1 time, in this way, total count will be 4 + 3 + 2 + 1 = 10. Actually, we have the formula n * (n – 1) / 2 = count. This solution is a bit overhead. First because k will be double, when we store double in hashmap. There may be a chance that same number have different double value because of 1 or 2 last digit. 2nd, it doesn’t consider the overlapping points.
A nicer solution is from this post. The idea is that it checks each point. For all lines which passing this point, find the line which contains max number of points. After this point is checked, this point won’t involve in future check. The checking process is like below:
Assume:
x = x2 – x1
y = y2 – y1
It simplifies (x, y) = (x, y) / gcd(x, y). When we store this (x, y) / gcd(x, y) as key. This is actually the ration of line made by the 2 points. And we know when we iterate POINTi, any other points with same ration will fall in line passing through POINTi. This facilitates us that we don’t use double. One thing we need to pay attention is that we need to make sure (1, -1) and (-1, 1) go to same line, and (0, 1) and (0, -1) go to same line. In the original code, the special gcd function can make sure that (1, -1) / gcd(1, -1) and (-1, 1) / gcd(-1, 1) get same value. This is simple, but it hides the logic behind it. I prefer to manually check the sign.
Another trick is to store String type of (xy) as key. This will save us more work.
Next one is that we need to store the overlapping points.
In the end, we know that the max number of lines in this point is max number of points in a line it found, plus overlapping, plus the point itself.
Below is the code:
public static int maxPoints(Point[] points) {
HashMap<String, Integer> hm = new HashMap<>();
int ans = 0;
for (int i = 0; i < points.length; i++) {
int overlap = 0, max = 0;
hm.clear();
for (int j = i + 1; j < points.length; j++) {
int x = points[j].x - points[i].x, y = points[j].y - points[i].y;
if (x == 0 && y == 0) {
overlap++;
continue;
}
int gcd = gcd(x, y);
x /= gcd;
y /= gcd;
// fix the sign issue. (3, -1) and (-3, 1) should be in same line. (0, -1) and (0, 1) should be in same line.
if (x < 0 || (x == 0 && y < 0)) {
x = -x;
y = -y;
}
String key = String.valueOf(x) + String.valueOf(y);
int value = hm.getOrDefault(key, 0);
hm.put(key, value + 1);
max = Math.max(max, value + 1);
}
ans = Math.max(ans, max + overlap + 1);
}
return ans;
}
public static int gcd(int a, int b) {
while (b != 0) {
int tmp = b;
b = a % b;
a = tmp;
}
return Math.abs(a);
}
Check my code on github.