149. Max Points on a Line

First idea was relying on y = ax +b to get a = (y1-y0)/(x1-x0), b = y1-ax1. There 2 issues with this approach:

divide by 0 error when x1 == x0
precision issue caused by the fact that a is rational (eg, 1/3)

Another general problem we are facing regardless of which route we take: duplication

How does selected approach below solve above problems:

For issue #2, instead of storing the ratio, we store the slop a of a line as pair (y1-y0) and (x1-x0). Also we use gcd to consolidate pairs with same slop eg, (1, 3), (2, 6). All lines go through same point with same slop should be identical so we don't need to calculate b
for issue #1, the gcd of 0 and another number c is always c. That said, we will store (y1-y0) and 0 when x0 == x1. That said, dx will be 0 and dy will be 1

Tip with the selected approach below:

counters = collections.defaultdict(int) is inside i-loop rather than outside of i-loop

suppose point1, point2, point3 are on the same line and we put the counter outside of the i-loop: We will add point2 and point3 to the dict as i is indexing point1. Then when i is indexing point2, we will again add point3 to the dict, which lead to incorrect result.

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        if n <= 2:
            return n
        
        res = 0
        for i in range(n):
            duplicate = 0
            candidate = 0
            counters = collections.defaultdict(int)
            for j in range(i+1, n):
                deltaX = points[i][0] - points[j][0]
                deltaY = points[i][1] - points[j][1]
                
                if deltaX == 0 and deltaY == 0:
                    duplicate += 1
                    continue
                
                gcd = self.gcd(deltaX, deltaY)
                dx, dy = deltaX // gcd, deltaY // gcd
                counters[(dx, dy)] += 1
                candidate = max(candidate, counters[(dx, dy)])
            
            res = max(res, candidate + duplicate + 1)
            
        return res
    
    def gcd(self, a, b):
        return a if b == 0 else self.gcd(b, a % b)

149. Max Points on a Line - cocoder39/coco39_LC GitHub Wiki