#149
Max Points on a Line
Hard HashMap of reduced slopes
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Given points on a plane, return the largest number of them that lie on one straight line.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the most points on one straight line.
Why this works: fix one point; points on the same line through it share a slope. Store slopes as reduced (dy, dx) fractions to avoid decimals.
Example: [[1,1],[2,2],[3,3]]
from (1,1): (1,1) slope twice → 2 + 1 = 3 points✦Hints open one at a time
Fix one point as an anchor; points on the same line through it share the same slope.
Avoid floating-point slopes: store (dy, dx) reduced by their GCD with a fixed sign.
↗Approach
For each anchor, count other points by normalised slope in a map. The best line through this anchor has (max count + 1) points. Points are distinct, so no duplicate handling is needed.
</>Solution (Java)
import java.util.*;
class Solution {
public int maxPoints(int[][] points) {
int n = points.length, best = 1;
for (int i = 0; i < n; i++) {
Map<String, Integer> slopes = new HashMap<>();
for (int j = i + 1; j < n; j++) {
int dx = points[j][0] - points[i][0];
int dy = points[j][1] - points[i][1];
int g = gcd(Math.abs(dx), Math.abs(dy));
dx /= g;
dy /= g;
if (dx < 0 || (dx == 0 && dy < 0)) { dx = -dx; dy = -dy; } // one sign per direction
int c = slopes.merge(dy + "/" + dx, 1, Integer::sum);
best = Math.max(best, c + 1);
}
}
return best;
}
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}!Common mistake
Using double slopes — precision errors, and −0.0 vs 0.0 are different keys.
Complexity
- Time: O(n² log V) for the GCDs.
- Space: O(n).
Topic: Hashing
🎬 Episodes 37–39: video coming soon