Maximum Darts in a Circular Dartboard: Angular Sweep

You are given a list of darts, where darts[i] = [xi, yi] is the position of the i-th dart on a 2D plane, and an integer r. Return the maximum number of darts that can be enclosed by a circle of radius r.

This is LeetCode 1453: Maximum Number of Darts Inside of a Circular Dartboard, and it is one of the best problems for learning how angular sweep and computational geometry show up in algorithm design. The technique it teaches appears whenever you need to find an optimal placement of a shape over a set of points.

Why this problem matters

Geometric optimization problems are rare in interviews, but when they appear, they separate candidates who can reason about math from those who cannot. This problem forces you to think about a continuous search space (where should the circle go?) and reduce it to a finite set of candidates. That reduction is the core skill. It shows up in computational geometry, robotics path planning, and collision detection systems. Once you see how to anchor a continuous search to discrete points, you can apply the same idea to many spatial problems.

The key insight

If you could place the circle anywhere, there are infinitely many positions to try. But there is a key observation: the optimal circle always passes through at least one dart, and often two. Why? If the optimal circle does not touch any dart on its boundary, you can slide it until it does, without losing any enclosed darts. That means you only need to consider circles that pass through at least one point.

The brute force approach considers all pairs of darts. For each pair within distance 2r, you compute the (up to two) circles of radius r that pass through both points. Then you count how many darts fall inside each candidate circle. The best count across all candidates is your answer.

But there is a faster approach: the angular sweep. For each dart as a "pivot," you look at all other darts within distance 2r. For each nearby dart, you compute the angular range where the circle of radius r centered along the arc would enclose that dart. Then you sweep through the angles, tracking how many darts are enclosed at each angle. This runs in O(n^2 log n) instead of the O(n^3) brute force.

The algorithm:

1. For each dart p, consider it as the pivot point that lies on the boundary of the circle.
2. For every other dart q within distance 2r of p, compute the angle from p to q and the angular half-width within which a circle through p also encloses q.
3. Create "enter" and "exit" events for each nearby dart. Sort them by angle.
4. Sweep through the events, tracking the current count. The maximum count (plus 1 for the pivot) across all pivots is the answer.

The solution

import math

def num_points(darts: list[list[int]], r: int) -> int:
    n = len(darts)
    if n == 1:
        return 1

    best = 1

    for i in range(n):
        events = []
        for j in range(n):
            if i == j:
                continue
            dx = darts[j][0] - darts[i][0]
            dy = darts[j][1] - darts[i][1]
            d = math.sqrt(dx * dx + dy * dy)
            if d > 2 * r:
                continue
            angle = math.atan2(dy, dx)
            delta = math.acos(d / (2 * r))
            events.append((angle - delta, 1))
            events.append((angle + delta, -1))

        events.sort(key=lambda e: (e[0], -e[1]))

        count = 1
        for _, typ in events:
            count += typ
            best = max(best, count)

    return best

Let's walk through what each piece does.

The outer loop picks each dart as the pivot. This is the point we guarantee lies on the boundary of our candidate circle.

For every other dart j, we compute the Euclidean distance from the pivot to dart j. If that distance exceeds 2r, no circle of radius r can pass through both points, so we skip it. Otherwise, we compute two values: the angle from the pivot to dart j (using atan2), and the angular half-width delta (using acos(d / (2r))). The half-width tells us how far the circle center can rotate around the pivot before dart j falls outside.

We create two events: an "enter" event at angle - delta (the dart enters the circle) and an "exit" event at angle + delta (the dart leaves). After sorting all events by angle, we sweep through them. Each enter event increments the count. Each exit event decrements it. The maximum count at any point during the sweep, plus 1 for the pivot itself, gives us the best enclosure for this pivot.

The sort(key=lambda e: (e[0], -e[1])) ensures that when two events have the same angle, enter events (+1) come before exit events (-1). This handles the boundary case where a dart is exactly at the edge of two candidate circles.

Visual walkthrough

Let's trace through the algorithm on a small example. Watch how we enumerate pairs, compute candidate circles, count enclosed points, and track the maximum.

For each pivot, the angular sweep finds the angle where the most darts overlap inside the circle. The total work is O(n) darts times O(n log n) for sorting events per pivot, giving O(n^2 log n) overall.

Complexity analysis

Time is O(n^2 log n). The outer loop runs n times (once per pivot). For each pivot, we examine up to n-1 other darts, create up to 2(n-1) events, and sort them in O(n log n). Total: n * O(n log n) = O(n^2 log n).

Space is O(n). For each pivot, we store at most 2(n-1) events. We reuse this list for each pivot, so the space is proportional to n.

The building blocks

1. Distance and angle computation

The foundation of this problem is computing the Euclidean distance between two points and the angle between them:

dx = x2 - x1
dy = y2 - y1
d = math.sqrt(dx * dx + dy * dy)
angle = math.atan2(dy, dx)

The distance tells you whether two points can share a circle of radius r (they must be within 2r). The angle gives you the direction from one point to another. These two computations are the atoms of computational geometry. You will use them in problems involving closest pairs, convex hulls, and any spatial query.

2. Angular sweep technique

The angular sweep is a way to turn a 2D geometric problem into a 1D sorting problem:

events = []
for nearby_point in nearby_points:
    angle = compute_angle(pivot, nearby_point)
    delta = compute_half_width(distance, r)
    events.append((angle - delta, 1))
    events.append((angle + delta, -1))

events.sort()
count = 0
for _, typ in events:
    count += typ
    best = max(best, count)

You project a geometric constraint (being inside a circle) onto a set of angular intervals. Then you sweep through sorted events to find the angle where the most intervals overlap. This is the same idea as the "meeting rooms" or "interval scheduling" pattern, but applied to angles instead of time.

Edge cases

Before submitting, think through these scenarios:

• Single dart: return 1. Any circle of radius r centered on it works.
• All darts at the same point: return n. A circle centered on that point encloses all of them.
• Two darts exactly 2r apart: they can both lie on a single circle of radius r. Return at least 2.
• All darts collinear: the angular sweep still works. The events just happen to be clustered along one direction.
• Floating point precision: use a small epsilon when comparing distances to r. The acos function can produce NaN if its argument slightly exceeds 1.0 due to floating point errors. Clamp the argument to [-1, 1].
• Large coordinates, small r: most pairs will be farther than 2r apart, so the inner loop skips them quickly. The algorithm is efficient even when few pairs are valid.

From understanding to recall

You have seen how angular sweep reduces a continuous geometric search to a discrete event-processing problem. The logic is elegant: fix a pivot, compute angular intervals for nearby darts, sweep to find the maximum overlap. But reproducing this under pressure requires remembering several details. How do you compute the angular half-width? Which direction do you sort events when angles tie? Do you add 1 for the pivot before or after sweeping?

These are not conceptual gaps. They are recall gaps. Spaced repetition closes them. You practice writing the distance computation, the event generation, and the sweep loop from memory at increasing intervals. After a few rounds, the angular sweep template is automatic. You see "maximize points inside a circle" in a problem statement, and the geometry flows out without hesitation.

Related posts

• Max Points on a Line - Another geometry problem counting points with a constraint
• Erect the Fence - Convex hull geometry problem
• K Closest Points to Origin - Distance computation fundamentals

CodeBricks breaks Maximum Darts in a Circular Dartboard into its distance computation and angular sweep building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a geometry problem shows up in your interview, you do not think about it. You just write it.