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.
Bob knows the positions of the n darts on the wall. He wants to place a dartboard of radius r on the wall so that the maximum number of darts that Alice throws lie on the dartboard.
Given the integer r, return the maximum number of darts that can lie on the dartboard.
Example 1:
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.
Example 2:
Input: darts = [[-3,0],[3,0],[2,6],[5,4],[0,9],[7,8]], r = 5 Output: 5 Explanation: Circle dartboard with center in (0,4) and radius = 5 contain all points except the point (7,8).
Constraints:
1 <= darts.length <= 100darts[i].length == 2-104 <= xi, yi <= 104darts are unique1 <= r <= 5000Problem 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.
This approach leverages the fact that any two darts that can be endpoints of a circle's diameter can serve as a potential center. For each pair of darts, we calculate possible centers of dartboards of radius r such that both darts lie on the circle's circumference. Then, for each center we calculate, we check how many other darts fall within a circle centered at that point with radius r.
The function get_circle_center calculates the potential circle centers such that two darts are on the circle's border. For each pair of darts, we calculate two possible centers and count how many points lie inside. We keep track of the maximum count found.
Time Complexity: O(n^3), where n is the number of darts because we check every pair of darts and potentially all other darts for inclusion.
Space Complexity: O(1), excluding input and output storage.
This approach involves a randomized technique with fixed center calculations. By randomly picking a dart and considering it as a center, we calculate each other dart's direction relative to it, choose another dart on the edge, and define potential centers. We calculate how many darts fit for every possible circle centered at each result.
In this solution, we iterate over the dart pairs to calculate potential centers using the method getCircleCenters. Each potential center is evaluated to count how many darts can be enclosed within a circle of radius r. We aim to maximize this count.
Time Complexity: O(n^3), considering the evaluation of each dart pair and checking membership for each dart.
Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Geometric Approach with Midpoint Circle Centers | Time Complexity: |
| Advanced Computational Geometry Solution Using Random Centering | Time Complexity: |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Geometric Pair Centers | O(n^3) | O(1) | Best deterministic solution for interview settings and small n (≤100) |
| Random Centering (Monte Carlo) | Expected O(k·n) | O(1) | When exploring probabilistic optimization or large datasets |
1453. Maximum Number of Darts Inside of a Circular Dartboard (Leetcode Hard) • Programming Live with Larry • 640 views views
Watch 4 more video solutions →Practice Maximum Number of Darts Inside of a Circular Dartboard with our built-in code editor and test cases.
Practice on FleetCode