Max Points on a Line
Created: April 7, 2020 by [lek-tin]
Last updated: April 7, 2020
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
Example 1
Input: [[1,1],[2,2],[3,3]]
Output: 3
Explanation:
^
|
| o
| o
| o
+------------->
0 1 2 3 4
Example 2
Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation:
^
|
| o
| o o
| o
| o o
+------------------->
0 1 2 3 4 5 6
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.
Solution
class Solution:
def maxPoints(self, points: List[List[int]]) -> int:
# If there are only 1 or 2 points in total
# they must be on the same line.
n = len(points)
if n < 3:
return n
def max_points_on_a_line_containing_point_i(i):
"""
Compute the max number of points
for a line containing point i.
"""
def add_line(i, j, count, duplicates):
"""
Add a line passing through i and j points.
Update max number of points on a line containing point i.
Update a number of duplicates of i point.
"""
# rewrite points as coordinates
x1 = points[i][0]
y1 = points[i][1]
x2 = points[j][0]
y2 = points[j][1]
# add a duplicate point
if x1 == x2 and y1 == y2:
duplicates += 1
# add a horizontal line : y = const
elif y1 == y2:
nonlocal horizontal_lines
horizontal_lines += 1
count = max(horizontal_lines, count)
# add a line : x = slope * y + c
# only slope is needed for a hash-map
# since we always start from the same point
else:
slope = (x1 - x2) / (y1 - y2)
lines[slope] = lines.get(slope, 1) + 1
count = max(lines[slope], count)
return count, duplicates
# init lines passing through point i
lines, horizontal_lines = {}, 1
# One starts with just one point on a line : point i.
count = 1
# point i is not a duplicate
duplicates = 0
# Compute lines passing through point i (fixed)
# and point j (interation).
# Update in a loop the number of points on a line
# and the number of duplicates of point i.
for j in range(i + 1, n):
count, duplicates = add_line(i, j, count, duplicates)
return count + duplicates
max_count = 1
# Compute in a loop a max number of points
# on a line containing point i.
for i in range(n - 1):
max_count = max(max_points_on_a_line_containing_point_i(i), max_count)
return max_count