Skip to main content
Talentd

Maximum Number of Darts Inside of a Circular Dartboard - Solution & Explanation

HardArrayMathGeometry11 min readAsked at: Meta
Practice this problem

Problem Statement

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 <= 100
  • darts[i].length == 2
  • -104 <= xi, yi <= 104
  • All the darts are unique
  • 1 <= r <= 5000

Approach Overview

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.

Approach 1: Geometric Approach with Midpoint Circle Centers

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.

Code

PythonJava

Python

Java

Complexity

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.

Try this approach in the editor →

Approach 2: Advanced Computational Geometry Solution Using Random Centering

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.

Code

C++C#

C++

C#

Complexity

Time Complexity: O(n^3), considering the evaluation of each dart pair and checking membership for each dart.
Space Complexity: O(1).

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJava

Python

Java

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Geometric Approach with Midpoint Circle Centers

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.

Advanced Computational Geometry Solution Using Random Centering

Time Complexity: O(n^3), considering the evaluation of each dart pair and checking membership for each dart.
Space Complexity: O(1).

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Geometric Pair CentersO(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

Video Solution

1453. Maximum Number of Darts Inside of a Circular Dartboard (Leetcode Hard) • Programming Live with Larry • 656 views views

Watch 4 more video solutions →

Frequently Asked Questions

Is Maximum Number of Darts Inside of a Circular Dartboard easy or hard?
The problem is classified as Hard on LeetCode because it requires geometric reasoning rather than common algorithm templates. Candidates must derive circle centers from pairs of points and carefully handle precision when checking distances within radius r.
Maximum Number of Darts Inside of a Circular Dartboard Python/Java solution
Python and Java implementations usually iterate through every pair of points, compute the two possible circle centers with radius r, and count how many points lie inside each circle. Distance checks use the Euclidean formula with floating-point comparisons. The overall complexity is O(n^3) with constant extra space.
How to solve Maximum Number of Darts Inside of a Circular Dartboard in O(n)?
An exact deterministic O(n) algorithm is not known for the general case. However, randomized methods can approximate the optimal center by sampling candidate circle centers and counting points inside. Each iteration runs in O(n), and with enough samples the expected runtime becomes O(k·n) while producing near-optimal results.
What is the best approach for Maximum Number of Darts Inside of a Circular Dartboard?
The most reliable approach computes circle centers defined by every pair of darts whose distance is at most 2r. Each pair produces up to two valid centers of a circle with radius r. Counting how many darts fall inside each candidate circle gives the maximum. This deterministic geometric approach runs in O(n^3) time and is widely accepted in interviews.
Is Maximum Number of Darts Inside of a Circular Dartboard asked at Google/Amazon/Meta?
Geometry-heavy problems like this appear in interviews at companies such as Google and Meta, especially for roles that emphasize algorithmic problem solving. It tests understanding of coordinate geometry, distance calculations, and careful floating-point handling rather than standard data structures alone.
What data structure is used in Maximum Number of Darts Inside of a Circular Dartboard?
The input is typically stored as an array of coordinate pairs. The main logic relies on geometric calculations such as Euclidean distance, midpoints, and perpendicular offsets. No complex data structures are required beyond iterating through the array and tracking counts.
What is the time complexity of Maximum Number of Darts Inside of a Circular Dartboard?
The standard geometric solution runs in O(n^3) time. You examine O(n^2) pairs of darts, compute up to two candidate circle centers, and count points inside the circle in O(n). Space complexity remains O(1) because only a few variables are used for distance and center calculations.

Ready to solve this problem?

Practice Maximum Number of Darts Inside of a Circular Dartboard with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays