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
#                 done.add((slope, yint))
#                 currPoints = 0
#                 for x, y in points:
#                     if xdiff * (b[1] - y) == (b[0] - x) * ydiff:
#                         currPoints += 1
#                 maxPoints = max(maxPoints, currPoints)
#         maxPoints = max(maxPoints, 1)
#         return maxPoints