Maximum Number of Darts Inside of a Circular Dartboard LeetCode solution in Python

1
# Runtime: 275 ms (Top 78.13%) | Memory: 14.5 MB (Top 9.38%)
2
class Solution:
3
    def numPoints(self, points: List[List[int]], r: int) -> int:
4

5
        def getPointsInside(i, r, n):
6
            # This vector stores alpha and beta and flag
7
            # is marked true for alpha and false for beta
8
            angles = []
9

10
            for j in range(n):
11

12
                if i != j and distance[i][j] <= 2 * r:
13
                    # acos returns the arc cosine of the complex
14
                    # used for cosine inverse
15
                    B = math.acos(distance[i][j] / (2 * r))
16

17
                    # arg returns the phase angle of the complex
18
                    x1, y1 = points[i]
19
                    x2, y2 = points[j]
20

21
                    A = math.atan2(y1 - y2, x1 - x2)
22

23
                    alpha = A - B
24

25
                    beta = A + B
26

27
                    angles.append((alpha, False))
28

29
                    angles.append((beta, True))
30

31
            # angles vector is sorted and traversed
32
            angles.sort()
33
            # count maintains the number of points inside
34
            # the circle at certain value of theta
35
            # res maintains the maximum of all count
36
            cnt, res = 1, 1
37
            for angle in angles:
38
                # entry angle
39
                if angle[1] == False:
40
                    cnt += 1
41
                # exit angle
42
                else:
43
                    cnt -= 1
44

45
                res = max(cnt, res)
46

47
            return res
48

49
        # Returns count of maximum points that can lie
50
        # in a circle of radius r.
51
        # a dis array stores the distance between every
52
        # pair of points
53
        n = len(points)
54
        max_pts = n
55
        distance = [[0 for _ in range(max_pts)] for _ in range(max_pts)]
56
        for i in range(n - 1):
57
            for j in range(i + 1, n):
58
                # abs gives the magnitude of the complex
59
                # number and hence the distance between
60
                # i and j
61
                x1, y1 = points[i]
62
                x2, y2 = points[j]
63
                distance[i][j] = distance[j][i] = sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
64

65
        # This loop picks a point p
66
        ans = 0
67
        # maximum number of points for point arr[i]
68
        for i in range(n):
69
            ans = max(ans, getPointsInside(i, r, n))
70

71
        return ans