[LeetCode] 149. Max Points on a Line

Problem : https://leetcode.com/problems/max-points-on-a-line/

A line is formed by 2 points. Points with same slops are on the same line.

Slop of  P1 and P2 =  ( P1. x - P2.x ) / (P1.y - P1. y).

Use (P1.x - P2.x),  (P1.y - P1.y) as key to save the counter of points with same slop.

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        @lru_cache(maxsize = None)
        def gcd(a, b):
            return a if b == 0 else gcd(b, a % b)
        
        result = 0

        for i in range(len(points)):
            # init duplicated = 1 for counting the point itself
            duplicated = 1
                
            # count of pointer with same slop
            slops = defaultdict(int)
            
            for j in range(i+1, len(points)):
                
                if points[i][0] == points[j][0] and points[i][1] == points[j][1]:
                    duplicated += 1
                else:
                    dx = points[j][0] - points[i][0]
                    dy = points[j][1] - points[i][1]
                    
                    d = gcd(dx, dy)
                    
                    slops[(dx/d, dy/d)] += 1
            
            result = max(result, duplicated)
            
            for _, count in slops.items():
                result = max(result, count + duplicated)
        
        return result