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
points
are unique.This problem asks to find the maximum number of points that lie on the same straight line given a set of points in a 2D plane.
This approach checks every pair of points to determine the line they define, and then counts how many other points lie on that line. This is computationally expensive.
Time Complexity: O(n³), where n is the number of points. This is because we have three nested loops: the outer two loops iterate through all pairs of points (O(n²)), and the inner loop iterates through the remaining points to check collinearity (O(n)).
Space Complexity: O(1). We only use a few variables to store coordinates and counts.
Code (Python):
class Solution:
def maxPoints(self, points: List[List[int]]) -> int:
n = len(points)
ans = 1
for i in range(n):
x1, y1 = points[i]
for j in range(i + 1, n):
x2, y2 = points[j]
cnt = 2
for k in range(j + 1, n):
x3, y3 = points[k]
a = (y2 - y1) * (x3 - x1)
b = (y3 - y1) * (x2 - x1)
cnt += a == b
ans = max(ans, cnt)
return ans
This approach is significantly more efficient. Instead of directly comparing points, we use the slope between pairs of points to identify points on the same line. Points (x1, y1) and (x2, y2) have the slope (y2-y1)/(x2-x1). If another point (x3, y3) is collinear, it will have the same slope when compared to (x1, y1) or (x2, y2). However, we need to handle vertical lines (infinite slope) and duplicate points carefully.
Time Complexity: O(n²), We iterate through pairs of points which is O(n²). The inner loop operations are all constant time.
Space Complexity: O(n), The hash map/dictionary used to store slopes can potentially store up to n entries in the worst case (all points lie on the same line).
Code (Python):
from collections import Counter
from math import gcd
class Solution:
def maxPoints(self, points: List[List[int]]) -> int:
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
n = len(points)
max_points = 1
for i in range(n):
duplicates = 1
slope_counts = Counter() # Store slopes and their counts
x1, y1 = points[i]
for j in range(i + 1, n):
x2, y2 = points[j]
if x2 == x1 and y2 == y1:
duplicates += 1
continue # Skip duplicate points
dx = x2 - x1
dy = y2 - y1
common_divisor = gcd(dx, dy)
slope = (dx // common_divisor, dy // common_divisor)
slope_counts[slope] += 1
max_points = max(max_points, duplicates + max(slope_counts.values(), default=0))
return max_points
The code uses Counter
for efficient counting of slopes and gcd
to normalize slopes. This avoids issues with floating-point comparisons. This refined approach provides a substantial improvement in efficiency compared to the brute force method. The handling of duplicate points is also crucial for correctness.