#1453

Hard

LeetCode Problem Workspace

Maximum Number of Darts Inside of a Circular Dartboard

Maximize the number of darts on a circular dartboard given dart positions and radius.

Problem Statement

Alice throws n darts on a wall, and the position of each dart is given by an array where darts[i] = [xi, yi] represents the ith dart's position. Bob knows the positions of the darts and needs to place a circular dartboard of radius r on the wall such that the maximum number of darts land within the dartboard.

Your task is to determine the maximum number of darts that can lie inside a dartboard of radius r. You may move the dartboard as needed to achieve this, ensuring the darts fall within its bounds.

Examples

Example 1

Input: darts = [[-2,0],[2,0],[0,2],[0,-2]], r = 2

Output: 4

Circle dartboard with center in (0,0) and radius = 2 contain all points.

Example 2

Input: darts = [[-3,0],[3,0],[2,6],[5,4],[0,9],[7,8]], r = 5

Output: 5

Circle dartboard with center in (0,4) and radius = 5 contain all points except the point (7,8).

Constraints

1 <= darts.length <= 100
darts[i].length == 2
-104 <= xi, yi <= 104
All the darts are unique
1 <= r <= 5000

Solution Approach

Optimal Dartboard Placement

The key observation is that an optimal placement of the dartboard can always be made so that two darts lie on the boundary. This reduces the problem to finding the maximum number of darts inside a circle whose boundary contains two specific darts.

Mathematical Computation of Distances

Once the center of the dartboard is determined, compute the distance from each dart to the center. Darts within the radius are counted as inside the dartboard. The Euclidean distance formula can be used to compute the distances efficiently.

Brute Force with Optimization

A brute-force solution involves calculating the number of darts inside each possible dartboard configuration, but optimizing the solution by reducing redundant computations can help improve performance. Using techniques like sorting or checking distances only when necessary can reduce time complexity.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the approach. The brute-force solution would involve checking all pairs of darts, which gives an O(n^2) time complexity. The optimized approach can reduce this complexity by pruning unnecessary checks, though it may still depend on dart positions and the number of darts, typically achieving a time complexity of O(n^2) in the worst case.

What Interviewers Usually Probe

The candidate understands how to handle geometric problems efficiently.
The candidate demonstrates familiarity with the Euclidean distance and circle geometry.
The candidate can identify trade-offs between brute-force and optimized approaches in geometry-based problems.

Common Pitfalls or Variants

Common pitfalls

Failing to properly compute the distance between two points using the Euclidean formula.
Not recognizing that the dartboard can be moved to optimize dart inclusion.
Not optimizing the solution by reusing computations for the same dartboard placement.

Follow-up variants

What if the dartboard had a different shape, such as an ellipse instead of a circle?
What if we were asked to maximize darts inside multiple dartboards of fixed size?
How would the solution change if dartboard placement was restricted to certain regions of the wall?

FAQ

What is the primary challenge in solving the Maximum Number of Darts Inside of a Circular Dartboard problem?

The main challenge lies in efficiently placing the dartboard to fit the maximum number of darts while minimizing unnecessary calculations, typically using geometric insights.

How do you determine the best placement of the dartboard?

The best placement involves finding two darts that can lie on the boundary of the dartboard, then counting how many other darts fit within the resulting circle.

How does the Euclidean distance formula come into play in this problem?

The Euclidean distance formula is used to calculate the distance from the center of the dartboard to each dart's position, determining if the dart lies inside the circle.

Can you optimize the brute-force solution for this problem?

Yes, optimizations such as pruning unnecessary checks and sorting the darts based on proximity can reduce the time complexity from O(n^3) to O(n^2).

What is the time complexity of the Maximum Number of Darts Inside of a Circular Dartboard problem?

The time complexity can range from O(n^2) to higher, depending on the approach used. The brute-force solution typically has O(n^2) complexity in the worst case.

terminal

Solution

Solution 1

#### Python3

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

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

Continue Practicing

#1515 best position for a service centre #1610 maximum number of visible points #1266 minimum time visiting all points