## DEV Community

Abhishek Chaudhary

Posted on

# Max Points on a Line

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`
• All the `points` are unique.

SOLUTION:

``````class Solution:
def maxPoints(self, points: List[List[int]]) -> int:
n = len(points)
maxPoints = float('-inf')
for i in range(n):
for j in range(i + 1, n):
a = points[i]
b = points[j]
xdiff = a[0] - b[0]
ydiff = a[1] - b[1]
xsm, xbig = b[0], a[0]
ysm, ybig = b[1], a[1]
if a[0] < b[0]:
xsm, xbig = a[0], b[0]
if a[1] < b[1]:
ysm, ybig = a[1], b[1]
currPoints = 2
for x, y in points:
if x >= xsm and x <= xbig and y >= ysm and y <= ybig:
if tuple(a) != (x, y) and tuple(b) != (x, y) and xdiff * (b[1] - y) == (b[0] - x) * ydiff:
currPoints += 1
maxPoints = max(maxPoints, currPoints)
maxPoints = max(maxPoints, 1)
return maxPoints

# class Solution:
#     def maxPoints(self, points):
#         n = len(points)
#         maxPoints = float('-inf')
#         done = set()
#         for i in range(n):
#             for j in range(i + 1, n):
#                 a = points[i]
#                 b = points[j]
#                 xdiff = a[0] - b[0]
#                 ydiff = a[1] - b[1]
#                 slope = ydiff / xdiff if xdiff != 0 else float('inf') if ydiff > 0 else float('-inf')
#                 yint = a[1] - slope * a[0]
#                 if (slope, yint) in done:
#                     continue