Max Points on a Line 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.
Example 1:


Input: points = [[1,1],[2,2],[3,3]] Output: 3
Example 2:


Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]] Output: 4
Constraints:
1 <= points.length <= 300
points[i].length == 2
-104 <= xi, yi <= 104
- All the
points
are unique.
Max Points on a Line Solutions
✅Time: O(n)
✅Space: O(n)
C++
class Solution {
public:
int maxPoints(vector<vector<int>>& points) {
int ans = 0;
for (int i = 0; i < points.size(); ++i) {
unordered_map<pair<int, int>, int, pairHash> slopeCount;
const vector<int> p1{points[i]};
int samePoints = 1;
int maxPoints = 0; // maximum number of points with the same slope
for (int j = i + 1; j < points.size(); ++j) {
const vector<int> p2{points[j]};
if (p1 == p2)
++samePoints;
else
maxPoints = max(maxPoints, ++slopeCount[getSlope(p1, p2)]);
}
ans = max(ans, samePoints + maxPoints);
}
return ans;
}
private:
pair<int, int> getSlope(const vector<int>& p1, const vector<int>& p2) {
const int dx = p2[0] - p1[0];
const int dy = p2[1] - p1[1];
if (dx == 0)
return {0, p1[0]};
if (dy == 0)
return {p1[1], 0};
const int d = __gcd(dx, dy);
return {dx / d, dy / d};
}
struct pairHash {
size_t operator()(const pair<int, int>& p) const {
return p.first ^ p.second;
}
};
};
Java
class Solution {
public int maxPoints(int[][] points) {
int ans = 0;
for (int i = 0; i < points.length; ++i) {
Map<Pair<Integer, Integer>, Integer> slopeCount = new HashMap<>();
int[] p1 = points[i];
int samePoints = 1;
int maxPoints = 0; // maximum number of points with the same slope
for (int j = i + 1; j < points.length; ++j) {
int[] p2 = points[j];
if (p1[0] == p2[0] && p1[1] == p2[1])
++samePoints;
else {
Pair<Integer, Integer> slope = getSlope(p1, p2);
slopeCount.merge(slope, 1, Integer::sum);
maxPoints = Math.max(maxPoints, slopeCount.get(slope));
}
}
ans = Math.max(ans, samePoints + maxPoints);
}
return ans;
}
private Pair<Integer, Integer> getSlope(int[] p1, int[] p2) {
final int dx = p2[0] - p1[0];
final int dy = p2[1] - p1[1];
if (dx == 0)
return new Pair<>(0, p1[0]);
if (dy == 0)
return new Pair<>(p1[1], 0);
final int d = gcd(dx, dy);
return new Pair<>(dx / d, dy / d);
}
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}
Python
class Solution:
def maxPoints(self, points: List[List[int]]) -> int:
ans = 0
def gcd(a: int, b: int) -> int:
return a if b == 0 else gcd(b, a % b)
def getSlope(p1: List[int], p2: List[int]) -> Tuple[int, int]:
dx = p2[0] - p1[0]
dy = p2[1] - p1[1]
if dx == 0:
return (0, p1[0])
if dy == 0:
return (p1[1], 0)
d = gcd(dx, dy)
return (dx // d, dy // d)
for i, p1 in enumerate(points):
slopeCount = defaultdict(int)
samePoints = 1
maxPoints = 0
for j in range(i + 1, len(points)):
p2 = points[j]
if p1 == p2:
samePoints += 1
else:
slope = getSlope(p1, p2)
slopeCount[slope] += 1
maxPoints = max(maxPoints, slopeCount[slope])
ans = max(ans, samePoints + maxPoints)
return ans
Watch Tutorial
Checkout more Solutions here