LeetCode 1453 - Maximum Number of Darts Inside of a Circular Dartboard

LeetCode Problem 1453

Difficulty: 🔴 Hard
Topics: Array, Math, Geometry

Solution

Problem Understanding

In this problem, we are given the coordinates of several darts thrown onto a 2D plane. Each dart is represented as a point (x, y). We are also given a radius r, which represents the radius of a circular dartboard.

The task is to place a circle of radius r somewhere on the plane so that the number of darts lying inside or exactly on the boundary of the circle is maximized. We must return that maximum number.

The important detail is that the center of the circle is not fixed. We may place it anywhere on the plane, including non integer coordinates. Because of this, the challenge is not simply checking existing points, but determining which circle placements are optimal.

The input constraints are relatively small:

• At most 100 points
• Coordinates can be large, up to 10^4
• Radius can be as large as 5000

Since there are only 100 points, algorithms around O(n^3) are acceptable, while O(n^4) approaches may become too slow.

An important geometric observation is that if a circle contains the optimal set of points, then we can usually move the circle until at least two points lie on its boundary, without decreasing the number of covered points. This dramatically reduces the search space.

There are several important edge cases:

• Only one dart exists, the answer must be 1.
• Multiple darts may already fit inside a single circle centered at one dart.
• Two points farther apart than 2r cannot lie on the same boundary circle of radius r.
• Floating point precision matters because circle centers are computed using square roots and division.
• Some points may lie exactly on the boundary, these must count as inside the dartboard.

Approaches

Brute Force Approach

A naive approach would attempt to test many possible circle centers across the plane and count how many points each circle contains.

One way to think about brute force is:

1. Generate candidate centers from a dense grid.
2. For each center, compute distances to all points.
3. Count how many points are within radius r.

This is clearly impractical because the plane is continuous, meaning infinitely many possible centers exist. Even discretizing the plane would not guarantee correctness.

Another brute force idea is to consider every triple of points and compute circles passing through them. However, circle fitting for triples becomes unnecessarily complicated and still leads to high complexity.

The brute force concept helps reveal an important property: the optimal circle is tightly constrained by points on its boundary.

Key Insight

If a circle of radius r contains multiple points, we can slide the circle around until one or two points touch the boundary while still preserving all covered points.

For any pair of points whose distance is at most 2r, there are exactly two circles of radius r passing through both points.

This means:

• Every meaningful candidate circle can be generated from a pair of points.
• We only need to examine circles defined by pairs of darts.

The algorithm therefore becomes:

1. Pick every pair of points.
2. Compute the possible circle centers of radius r passing through them.
3. Count how many darts each circle contains.
4. Track the maximum.

Since there are only 100 points, this approach is efficient enough.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Infinite or impractical	O(1)	Continuous search space of circle centers
Optimal	O(n³)	O(1)	Generate candidate circles from point pairs

Algorithm Walkthrough

1. Start with the answer initialized to 1, because any single dart can always be covered by a circle centered at that dart.
2. Iterate through every pair of points (p1, p2).
3. Compute the Euclidean distance between the two points.
4. If the distance is greater than 2r, skip this pair because no circle of radius r can pass through both points.
5. Otherwise, compute the midpoint between the two points. This midpoint lies on the line segment connecting them.
6. The circle center must lie on the perpendicular bisector of the segment connecting the points.
7. Compute the distance from the midpoint to the circle center using geometry:

The triangle formed by:

• the center,
• the midpoint,
• one endpoint

is a right triangle.

Using the Pythagorean theorem:

$h = \sqrt{r^2 - \left(\frac{d}{2}\right)^2}$

where:

• d is the distance between the points
• h is the distance from midpoint to circle center

8. Determine the perpendicular direction vector.
9. Using the midpoint and perpendicular vector, compute the two possible circle centers.
10. For each candidate center:

• Iterate through all darts.
• Compute the distance from the center to the dart.
• Count the dart if the distance is less than or equal to r.

11. Update the maximum count.
12. After all pairs are processed, return the maximum.

Why it works

Any optimal circle can be translated until at least two contained points touch the boundary of the circle. Therefore, every optimal solution corresponds to a circle generated from some pair of points.

By examining every valid pair and both possible circle centers derived from that pair, we guarantee that the optimal circle configuration is considered. Counting all points inside each candidate circle ensures the maximum possible number is found.

Python Solution

from typing import List
import math

class Solution:
    def numPoints(self, darts: List[List[int]], r: int) -> int:
        n = len(darts)

        if n == 1:
            return 1

        EPSILON = 1e-7
        best = 1

        def count_points(cx: float, cy: float) -> int:
            count = 0

            for x, y in darts:
                dx = x - cx
                dy = y - cy

                if dx * dx + dy * dy <= r * r + EPSILON:
                    count += 1

            return count

        for i in range(n):
            x1, y1 = darts[i]

            for j in range(i + 1, n):
                x2, y2 = darts[j]

                dx = x2 - x1
                dy = y2 - y1

                distance_sq = dx * dx + dy * dy
                distance = math.sqrt(distance_sq)

                if distance > 2 * r + EPSILON:
                    continue

                mid_x = (x1 + x2) / 2
                mid_y = (y1 + y2) / 2

                half_distance = distance / 2

                height = math.sqrt(r * r - half_distance * half_distance)

                perp_x = -dy / distance
                perp_y = dx / distance

                center1_x = mid_x + perp_x * height
                center1_y = mid_y + perp_y * height

                center2_x = mid_x - perp_x * height
                center2_y = mid_y - perp_y * height

                best = max(best, count_points(center1_x, center1_y))
                best = max(best, count_points(center2_x, center2_y))

        return best

The implementation follows the geometric derivation directly.

The helper function count_points counts how many darts lie inside a candidate circle. To avoid floating point precision issues, the comparison includes a small epsilon value.

The nested loops enumerate all point pairs. For each pair, the algorithm first checks whether the points are close enough to fit inside the same circle of radius r.

Once a valid pair is found, the midpoint is computed. Then the perpendicular bisector direction is calculated using the normalized perpendicular vector.

The geometry formula gives the offset distance from the midpoint to the circle center. Using both positive and negative perpendicular directions generates the two possible centers.

Finally, every dart is tested against both circles, and the maximum count is updated.

Go Solution

package main

import (
	"math"
)

func numPoints(darts [][]int, r int) int {
	n := len(darts)

	if n == 1 {
		return 1
	}

	const EPSILON = 1e-7

	best := 1
	radiusSquared := float64(r * r)

	countPoints := func(cx, cy float64) int {
		count := 0

		for _, point := range darts {
			dx := float64(point[0]) - cx
			dy := float64(point[1]) - cy

			if dx*dx+dy*dy <= radiusSquared+EPSILON {
				count++
			}
		}

		return count
	}

	for i := 0; i < n; i++ {
		x1 := float64(darts[i][0])
		y1 := float64(darts[i][1])

		for j := i + 1; j < n; j++ {
			x2 := float64(darts[j][0])
			y2 := float64(darts[j][1])

			dx := x2 - x1
			dy := y2 - y1

			distanceSquared := dx*dx + dy*dy
			distance := math.Sqrt(distanceSquared)

			if distance > float64(2*r)+EPSILON {
				continue
			}

			midX := (x1 + x2) / 2.0
			midY := (y1 + y2) / 2.0

			halfDistance := distance / 2.0

			height := math.Sqrt(float64(r*r) - halfDistance*halfDistance)

			perpX := -dy / distance
			perpY := dx / distance

			center1X := midX + perpX*height
			center1Y := midY + perpY*height

			center2X := midX - perpX*height
			center2Y := midY - perpY*height

			best = max(best, countPoints(center1X, center1Y))
			best = max(best, countPoints(center2X, center2Y))
		}
	}

	return best
}

func max(a, b int) int {
	if a > b {
		return a
	}

	return b
}

The Go implementation mirrors the Python logic closely. Since Go does not provide a built in max function for integers, a helper function is added.

All geometric calculations use float64 because integer arithmetic would lose precision during midpoint and square root calculations.

The solution uses slices for storing points, matching the LeetCode function signature directly.

Worked Examples

Example 1

Input:

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

The points form a cross centered around the origin.

Consider the pair (-2,0) and (2,0).

Step	Value
Distance	4
2r	4
Midpoint	(0, 0)
Half distance	2
Height	0

Since the height is 0, there is only one possible center:

Center = (0, 0)

Now count points inside radius 2.

Point	Distance to Center	Inside
(-2,0)	2	Yes
(2,0)	2	Yes
(0,2)	2	Yes
(0,-2)	2	Yes

Count becomes 4.

This is the optimal answer.

Example 2

Input:

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

Consider the pair (-3,0) and (3,0).

Step	Value
Distance	6
Midpoint	(0,0)
Half distance	3

Compute height:

$h = \sqrt{5^2 - 3^2} = 4$

The perpendicular direction is vertical, so the two centers are:

(0, 4)
(0, -4)

Testing center (0,4):

Point	Distance	Inside
(-3,0)	5	Yes
(3,0)	5	Yes
(2,6)	sqrt(8)	Yes
(5,4)	5	Yes
(0,9)	5	Yes
(7,8)	sqrt(65)	No

The count is 5, which becomes the final answer.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n³)	O(n²) pairs, each pair checks all n points
Space	O(1)	Only constant extra variables are used

The algorithm iterates through all pairs of points, which requires O(n²) work. For every generated circle center, it scans all points to count how many lie inside the circle, adding another factor of n.

Since n ≤ 100, the worst case is approximately 100³ = 1,000,000 operations, which is easily fast enough.

The algorithm uses only a fixed number of floating point variables and counters, so the extra space usage is constant.

Test Cases

from typing import List

class Solution:
    def numPoints(self, darts: List[List[int]], r: int) -> int:
        import math

        n = len(darts)

        if n == 1:
            return 1

        EPSILON = 1e-7
        best = 1

        def count_points(cx: float, cy: float) -> int:
            count = 0

            for x, y in darts:
                dx = x - cx
                dy = y - cy

                if dx * dx + dy * dy <= r * r + EPSILON:
                    count += 1

            return count

        for i in range(n):
            x1, y1 = darts[i]

            for j in range(i + 1, n):
                x2, y2 = darts[j]

                dx = x2 - x1
                dy = y2 - y1

                distance = math.sqrt(dx * dx + dy * dy)

                if distance > 2 * r + EPSILON:
                    continue

                mid_x = (x1 + x2) / 2
                mid_y = (y1 + y2) / 2

                half_distance = distance / 2

                height = math.sqrt(r * r - half_distance * half_distance)

                perp_x = -dy / distance
                perp_y = dx / distance

                center1_x = mid_x + perp_x * height
                center1_y = mid_y + perp_y * height

                center2_x = mid_x - perp_x * height
                center2_y = mid_y - perp_y * height

                best = max(best, count_points(center1_x, center1_y))
                best = max(best, count_points(center2_x, center2_y))

        return best

solution = Solution()

assert solution.numPoints([[-2,0],[2,0],[0,2],[0,-2]], 2) == 4
# all points exactly on boundary

assert solution.numPoints([[-3,0],[3,0],[2,6],[5,4],[0,9],[7,8]], 5) == 5
# sample case with one excluded point

assert solution.numPoints([[0,0]], 1) == 1
# single point

assert solution.numPoints([[0,0],[10,10]], 1) == 1
# points too far apart

assert solution.numPoints([[0,0],[1,0],[0,1],[1,1]], 1) == 4
# small square fully covered

assert solution.numPoints([[0,0],[2,0]], 1) == 2
# diameter exactly equals 2r

assert solution.numPoints([[0,0],[4,0],[8,0]], 2) == 2
# only adjacent points fit together

assert solution.numPoints([[1,2],[3,5],[6,7],[8,9]], 100) == 4
# huge radius covers everything

assert solution.numPoints([[0,0],[0,2],[2,0],[2,2],[1,1]], 2) == 5
# center point plus corners

Test	Why
Cross shaped sample	Validates boundary inclusion
Second sample	Validates geometric center computation
Single point	Smallest valid input
Distant points	Ensures invalid pairs are skipped
Small square	Tests multiple points inside one circle
Diameter equals 2r	Tests tangent case
Linear points	Ensures partial coverage handled correctly
Huge radius	Tests full coverage
Mixed interior and boundary points	Validates counting logic

Edge Cases

One important edge case occurs when the distance between two points is exactly 2r. In this situation, the two points lie on opposite ends of a diameter, and there is only one valid circle center. Numerically, this can cause floating point instability because the computed height becomes zero. The implementation handles this naturally because the perpendicular offset becomes zero, producing the same center twice.

Another important case is when all points are extremely far apart. A naive implementation might incorrectly attempt to compute circle centers for impossible pairs, leading to negative values inside the square root operation. The solution avoids this by first checking whether the distance exceeds 2r.

Floating point precision is another major concern. Due to rounding errors, points that mathematically lie exactly on the circle boundary might appear slightly outside when computed numerically. The implementation solves this using a small epsilon tolerance in comparisons.

A final subtle edge case occurs when only one dart exists. Since the pair iteration never executes, the answer must already be initialized correctly. Setting the initial answer to 1 guarantees correct behavior for this minimal input.