Maximum Number of Darts Inside of a Circular Dartboard — LeetCode 1453 Python Solution

HardGeometryArrayMath

Problem: #1453
Pattern: Math and Number Theory
Reading time: 6 min
Source: leetcode.com

The problem

Alice is throwing n darts on a very large wall. You are given an array darts where darts[i] = [xi, yi] is the position of the ith dart that Alice threw on the wall.

Example

Input: darts = [[-2,0],[2,0],[0,2],[0,-2]], r = 2
Output: 4
Explanation: Circle dartboard with center in (0,0) and radius = 2 contain all points.

Python solution

Python

class Solution:
    def numPoints(self, darts: list[list[int]], r: int) -> int:
        def countDarts(x, y):
            count = 0
            for x1, y1 in darts:
                if dist((x, y), (x1, y1)) <= r + 1e-7:
                    count += 1
            return count

        def possibleCenters(x1, y1, x2, y2):
            dx, dy = x2 - x1, y2 - y1
            d = sqrt(dx * dx + dy * dy)
            if d > 2 * r:
                return []
            mid_x, mid_y = (x1 + x2) / 2, (y1 + y2) / 2
            dist_to_center = sqrt(r * r - (d / 2) * (d / 2))
            offset_x = dist_to_center * dy / d
            offset_y = dist_to_center * -dx / d
            return [
                (mid_x + offset_x, mid_y + offset_y),
                (mid_x - offset_x, mid_y - offset_y),
            ]

        n = len(darts)
        max_darts = 1

        for i in range(n):
            for j in range(i + 1, n):
                centers = possibleCenters(
                    darts[i][0], darts[i][1], darts[j][0], darts[j][1]
                )
                for center in centers:
                    max_darts = max(max_darts, countDarts(center[0], center[1]))

        return max_darts

Complexity

Measure	Complexity
Time	O(n) or O(1)
Space	O(1) auxiliary

Pattern: Math and Number Theory

Find the closed form, the invariant, or the modular identity — and skip the loop entirely. LeetCode 1453. Maximum Number of Darts Inside of a Circular Dartboard is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Math and Geometry.

The math and number theory guide has the Python template for the pattern and the 485 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1453. Maximum Number of Darts Inside of a Circular Dartboard?: LeetCode 1453. Maximum Number of Darts Inside of a Circular Dartboard is rated Hard on LeetCode.
What topics does LeetCode 1453. Maximum Number of Darts Inside of a Circular Dartboard cover?: LeetCode 1453. Maximum Number of Darts Inside of a Circular Dartboard is tagged Geometry, Array and Math on LeetCode.