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.
1from collections import defaultdict
2from math import gcd
3
This implementation utilizes line equations represented in ax + by + c form, normalized using gcd, to track lines passing through each point. This avoids precision issues inherent with float slopes.