Fork me on GitHub

Max Points on a Line

Posted on

Description

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

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
# Definition for a point.
# class Point:
#     def __init__(self, a=0, b=0):
#         self.x = a
#         self.y = b

class Solution:
    def gcd(self, target):
        if target[0] == 0 or target[1] == 0:
            return 1
        left =abs(target[1])
        right =abs(target[0])
        while right % left != 0:
            temp = left
            left = right % left
            right = temp
            
        sign = 1 if target[0] > 0 else -1
        return left * sign
        
    def maxPoints(self, points):
        """
        :type points: List[Point]
        :rtype: int
        """
        if points is None or len(points) == 0:
            return 0
        if len(points) == 1:
            return 1
        
        points_gradient = [{} for i in range(len(points))]
        counter = [1 for i in range(len(points))]
        for i in range(len(points) - 1):
            for j in range(i + 1, len(points)):
                if (points[i].x == points[j].x and points[i].y == points[j].y):
                    counter[i] += 1
                    counter[j] += 1
                    continue
                
                raw_gradient = None
                if points[i].x == points[j].x:
                    raw_gradient = (1, 0)  
                elif points[i].y == points[j].y:
                    raw_gradient = (0, 1)
                else:
                    raw_gradient = ((points[i].y - points[j].y), (points[i].x - points[j].x))
                
                gradient = (raw_gradient[0] / self.gcd(raw_gradient), raw_gradient[1] / self.gcd(raw_gradient))
                
                if points_gradient[i].get(gradient) is None:
                    points_gradient[i][gradient] = 1
                else:
                    points_gradient[i][gradient] += 1
                if points_gradient[j].get(gradient) is None:
                    points_gradient[j][gradient] = 1
                else:
                    points_gradient[j][gradient] += 1
                    
        ret = -1
        print(points_gradient)
        for (index, item) in enumerate(points_gradient):
            ret = max(ret, (max(item.values()) if item else 0) + counter[index])
            
        return ret