Problem statement

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

Solution

For each pairs of points we can evaluate and hash line they are lying on: hash will be triple of coefficients (a, b, c) of equaltion of line, where we deal with gcd: (2, 4, 6) -> (1, 2, 3) and deal with signs. Also we need to deal with duplicate points.

Complexity

Time and space complexity is O(n^2). I think I saw the paper, that it can not be solved in faster time.

Code

class Solution:
    def maxPoints(self, points):
        points = list(Counter((x, y) for x, y in points).items())
        n = len(points)
        if n < 3: return sum(i for _,i in points)
        lines = defaultdict(set)
        
        for i in range(n):
            for j in range(i+1, n):
                (x1, y1), c1 = points[i]
                (x2, y2), c2 = points[j]
                a, b, c = y1 - y2, x2 - x1, x1*y2 - x2*y1
                d = gcd(gcd(a, b), c)
                a, b, c = a//d, b//d, c//d
                if a < 0 or a == 0 and b < 0: a, b, c = -a, -b, -c
                lines[a, b, c] |= set([i,j])

        return max(sum(points[i][1] for i in dr) for dr in lines.values())