149. Max Points on a Line
Description
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
Idea
The code below is my simple solution for this problem using gcd algorithm to calculate the gradients.
Solution
# Definition for a point.
# class Point:
# def __init__(self, a=0, b=0):
# self.x = a
# self.y = b
from math import gcd
class Solution:
def maxPoints(self, points):
"""
:type points: List[Point]
:rtype: int
"""
length = len(points)
if length <= 2:
return length
tmp = [{} for i in range(length)]
res = 2
for i in range(length):
# count the number of duplicated points for point i
duplicate = 1
for j in range(length):
if i == j:
continue
# count the gradient
# same point
if points[i].y == points[j].y and points[i].x == points[j].x:
duplicate += 1
continue
# vertical
elif points[i].x == points[j].x:
gradient = (0, 0)
else:
a = points[i].y - points[j].y
b = points[i].x - points[j].x
c = gcd(a, b)
gradient = (a // c, b // c)
if gradient not in tmp[i]:
tmp[i][gradient] = 0
tmp[i][gradient] += 1
if duplicate == length:
res = duplicate
break
result = max(tmp[i].values()) + duplicate
res = max(res, result)
return res