LeetCode Solutions Blog

Maximum Number of Darts Inside of a Circular Dartboard

Number: 1563

Difficulty: Hard

Paid? No

Companies: Meta

Problem Description

Given a set of points representing dart positions and a fixed radius r, find the placement of a circular dartboard (with radius r) that maximizes the number of darts on or inside its boundary.

Key Insights

The optimal circle can be determined by finding a circle that passes through two dart points.
For any pair of darts, if the distance between them is less than or equal to 2r, there exists one or two candidate circle centers that have both points on the boundary.
For each candidate center (and also considering the possibility of a circle centered exactly at one dart), count the number of darts that lie within the circle.
An O(n^3) approach is feasible since the maximum number of darts is 100.

Space and Time Complexity

Time Complexity: O(n^3) in the worst-case due to iterating over each pair (O(n^2)) and then counting inside each candidate circle (O(n)). Space Complexity: O(1) extra space beyond input storage.

Solution

The solution iterates through all pairs of darts. For each pair:

Calculate the distance between the two points.
If the distance is greater than 2r, skip because no circle exists with both points on its boundary.
Otherwise, compute the midpoint between the two darts.
Calculate the distance from the midpoint to the potential circle center (h = sqrt(r^2 - (d/2)^2)).
Determine the two candidate centers by offsetting the midpoint along the perpendicular direction.
For each candidate center, verify how many darts lie within the circle (distance ≤ r).
Also, check each dart position as a potential center.
Return the maximum count achieved.

Critical steps include handling the geometric computation for candidate circle centers and ensuring precision when comparing distances.

Code Solutions

import math

def numPoints(darts, r):
    # Function to count darts inside or on the circle given center (cx, cy)
    def count_darts(cx, cy):
        count = 0
        for x, y in darts:
            # Calculate square distance
            if (x - cx) ** 2 + (y - cy) ** 2 <= r * r + 1e-6:
                count += 1
        return count

    n = len(darts)
    if n == 0:
        return 0

    max_darts = 1  # At least one dart is inside if board centered on it

    # Check each dart position as a potential circle center
    for x, y in darts:
        max_darts = max(max_darts, count_darts(x, y))

    # Consider each pair of darts to form candidate circle centers
    for i in range(n):
        for j in range(i + 1, n):
            x1, y1 = darts[i]
            x2, y2 = darts[j]
            dx = x2 - x1
            dy = y2 - y1
            d_sq = dx * dx + dy * dy
            d = math.sqrt(d_sq)
            # If the distance between darts is more than 2r, they can't both lie on the circle's boundary
            if d > 2 * r:
                continue

            # Midpoint between the two darts
            midx = (x1 + x2) / 2.0
            midy = (y1 + y2) / 2.0

            # Distance from midpoint to the center of the circle along the perpendicular direction
            h = math.sqrt(r * r - (d / 2.0) ** 2)

            # Normalize the perpendicular direction vector (-dy, dx)
            norm = math.sqrt(dx * dx + dy * dy)
            ex = -dy / norm
            ey = dx / norm

            # Calculate both candidate centers using the perpendicular offset
            center1x = midx + ex * h
            center1y = midy + ey * h
            center2x = midx - ex * h
            center2y = midy - ey * h

            # Count the darts inside these candidate circles and update maximum
            max_darts = max(max_darts, count_darts(center1x, center1y), count_darts(center2x, center2y))

    return max_darts

# Example usage:
if __name__ == "__main__":
    darts1 = [[-2,0],[2,0],[0,2],[0,-2]]
    r1 = 2
    print(numPoints(darts1, r1))  # Expected output: 4

    darts2 = [[-3,0],[3,0],[2,6],[5,4],[0,9],[7,8]]
    r2 = 5
    print(numPoints(darts2, r2))  # Expected output: 5