Maximum Number of Darts Inside of a Circular Dartboard

Maximum Number of Darts Inside of a Circular Dartboard

What is this problem about?

The Maximum Number of Darts Inside of a Circular Dartboard coding problem gives you a set of dart positions on a 2D plane and a radius r. You need to place a circular dartboard of radius r anywhere on the plane to maximize the number of darts that land on or inside the circle. This is a computational geometry problem requiring careful circle placement optimization.

Why is this asked in interviews?

Meta uses this problem to test candidates' understanding of computational geometry and the insight that the optimal circle placement always has at least two darts on its boundary (or a single dart for the degenerate case). This observation reduces the infinite search space to a finite O(n²) set of candidate circles, making the problem tractable with O(n³) or O(n² log n) algorithms.

Algorithmic pattern used

Geometry with circle intersection enumeration: The key insight: the optimal circle either contains only 1 dart (place circle centered at that dart) or has ≥ 2 darts on its boundary. For every pair of darts (i, j) within distance 2r of each other, the circle of radius r passing through both has exactly 2 center positions. Enumerate all such candidate centers (O(n²) pairs → O(n²) centers). For each candidate center, count darts within radius r (O(n)). Total: O(n³).

To compute the two circle centers given two points and radius r:

• Midpoint M of the two points.
• Distance d between points.
• Height h = sqrt(r² - (d/2)²).
• Two centers are at M ± h * perpendicular_unit_vector.

Example explanation

Darts: [(−2,0), (2,0), (0,2)], r = 2.

• Pair (−2,0) and (2,0): distance=4=2r. Only one center: (0,0).
  • Count darts within r=2 of (0,0): |(−2,0)|=2 ✓, |(2,0)|=2 ✓, |(0,2)|=2 ✓. Count=3.
• Answer = 3.

All three darts lie on the circle of radius 2 centered at (0,0).

Common mistakes candidates make

• Only checking dart-centered circles: Missing pairs of darts on the boundary misses the optimal solution in many cases.
• Floating point precision: Circle center computation involves sqrt; use a small epsilon for distance comparisons (e.g., dist <= r + 1e-6).
• Not handling the case where two darts are more than 2r apart: Such pairs cannot both lie on a circle of radius r. Skip them to avoid taking sqrt of a negative number.

Interview preparation tip

For the Array Math Geometry interview pattern, always start geometric circle-placement problems with the observation: "the optimal circle's boundary passes through some of the input points." This reduces infinite continuous optimization to finite discrete enumeration. Pair this with careful floating-point handling (epsilon comparisons) and your solution will be both correct and robust.