Leetcode 149. Max Points on a Line

Seawolf

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

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        res = 0
        
        for i in range(n):
            hashmap = collections.defaultdict(int)
            local_max = 0
            same_point = 1
            n1 = points[i]
            
            for j in range(i + 1, n):
                n2 = points[j]
                if n1[0] == n2[0] and n1[1] == n2[1]:
                    same_point += 1
                else:
                    slope = self.get_slope(n1, n2)
                    hashmap[slope] = hashmap[slope] + 1
                    local_max = max(local_max, hashmap[slope])
                    
            res = max(res, local_max + same_point)
        
        return res
        
    def get_slope(self, n1: List[int], n2: List[int]) -> List[int]:
        dx = n2[0] - n1[0]
        dy = n2[1] - n1[1]

        if dy == 0:
            return (n1[1], 0)
        if dx == 0:
            return (0, n1[0])

        d = self.gcd(dx, dy)

        return (dy / d, dx / d)
    
    def gcd(self, a, b): 
        if(b==0): 
            return a 
        else: 
            return self.gcd(b,a%b)