Maximum Number of Darts Inside of a Circular Dartboard - Video Solutions

Problem Overview: You are given coordinates of darts on a 2D plane and a dartboard radius r. The goal is to place a circle of radius r anywhere on the plane so that it covers the maximum number of darts.

Approach 1: Geometric Approach with Midpoint Circle Centers (O(n³) time, O(1) space)

The key observation: if a circle of radius r contains two boundary points, its center must lie on one of the two circle centers formed by those points at distance r. Iterate over every pair of points. If their distance is ≤ 2r, compute the two possible circle centers that place both points on the boundary. For each candidate center, iterate through all points and count how many fall within distance ≤ r. Track the maximum count.

This approach uses basic geometry formulas for midpoint and perpendicular offsets to compute the two centers. Even though it requires checking all pairs and counting points for each candidate center, the constraints (typically ≤100 points) make O(n³) feasible. This method relies heavily on geometric distance calculations and works well when implementing deterministic solutions using math and geometry primitives.

Approach 2: Advanced Computational Geometry with Random Centering (Expected O(k·n) time, O(1) space)

This approach treats the circle center as a search problem. Instead of evaluating every pair deterministically, randomly sample candidate centers derived from pairs of points or nearby offsets. For each sampled center, compute how many darts lie within radius r using a simple distance check. Repeating the process multiple times increases the probability of discovering the optimal or near-optimal placement.

The algorithm relies on the fact that optimal centers often lie near circles defined by pairs of points. Random sampling avoids the full O(n²) pair enumeration and works well when performance matters for larger inputs. The counting step still scans all points in the array of coordinates, giving O(n) per iteration. Accuracy improves as the number of samples increases.

Recommended for interviews: The geometric pair-center approach is what most interviewers expect. It demonstrates understanding of circle geometry and careful handling of floating-point distance checks. Starting with the pair observation shows problem insight, and implementing the center calculation correctly proves strong algorithmic thinking. The randomized method is more advanced and useful when exploring computational geometry optimizations.