149. Max Points on a Line

Problem Link

Description

---

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

---

Python3

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        res = 0
        n = len(points)
        INT_MAX = 10 ** 5
        
        for i in range(n):
            x1, y1 = points[i]
            mp = collections.defaultdict(int)
            samePoints = 1
            
            for j in range(i + 1, n):
                x2, y2 = points[j]
                if x1 == x2 and y1 == y2:
                    samePoints += 1
                elif x1 == x2:
                    mp[INT_MAX] += 1
                else:
                    x, y = x2 - x1, y2 - y1
                    divisor = gcd(x, y)
                    x, y = x // divisor, y // divisor
                    mp[y / x] += 1
 
            mmax = max(mp.values() or [0])
            mmax += samePoints
            res = max(res, mmax)
                    
        return res