Sponsored
Sponsored
In this approach, for each point, we will calculate the slope it forms with every other point and store the slope in a hashmap. The number of points with the same slope from a given point can determine the number of points on the same line. We need to be careful with slope representation by using a reduced form using GCD to handle precision issues.
Time Complexity: O(n^2), where n is the number of points. This is because we check each pair of points which leads to n * (n-1)/2 slope calculations.
Space Complexity: O(n), for storing the slopes in the hashmap.
1from collections import defaultdict
2from math import gcd
3
4class Solution:
5 def maxPoints(self, points: list[list[int]]) -> int:
6 def calculate_slope(p1, p2):
7 dx = p2[0] - p1[0]
8 dy = p2[1] - p1[1]
9 if dx == 0:
10 return (float('inf'), 0)
11 if dy == 0:
12 return (0, float('inf'))
13 g = gcd(dx, dy)
14 return (dy // g, dx // g)
15
16 max_points = 1
17 n = len(points)
18 for i in range(n):
19 slope_count = defaultdict(int)
20 for j in range(n):
21 if i != j:
22 slope = calculate_slope(points[i], points[j])
23 slope_count[slope] += 1
24 max_points = max(max_points, slope_count[slope] + 1)
25 return max_pointsThe solution iterates over each point and calculates the slope with every other point, using a hashmap to track and count each slope. The greatest count of any slope originating from a point plus one (for the point itself) gives the maximum number of points on a line through that point.
Alternatively, instead of using slopes directly, we express a line using its coefficients in the line equation format ax + by + c = 0, using GCD to ensure uniqueness in line parameters. This approach confirms lines uniquely, facilitating easier comparisons.
Time Complexity: O(n^2), from comparing each pair of points.
Space Complexity: O(n), for storing normalized line equations.
1#include <vector>
2#include <unordered_map>
3#include <cmath>
4#include <tuple>
5using namespace std;
6
class Solution {
public:
int maxPoints(vector<vector<int>>& points) {
int n = points.size();
if (n <= 1) return n;
int max_points = 1;
for (int i = 0; i < n; ++i) {
unordered_map<string, int> line_count;
for (int j = 0; j < n; ++j) {
if (i != j) {
int a = points[i][1] - points[j][1];
int b = points[j][0] - points[i][0];
int c = points[i][0] * points[j][1] - points[j][0] * points[i][1];
int g = gcd(gcd(abs(a), abs(b)), abs(c));
a /= g;
b /= g;
c /= g;
string line = to_string(a) + '/' + to_string(b) + '/' + to_string(c);
line_count[line]++;
max_points = max(max_points, line_count[line] + 1);
}
}
}
return max_points;
}
};
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}The C++ solution builds on the ax + by + c line representation using gcd normalization, employing string keys for the cache to manage line counts efficiently.