Maximum Number of Darts Inside of a Circular Dartboard

Hard

#1343Time: O(n^3). There are two nested loops to iterate through all `O(n^2)` pairs of darts. For each pair, we find two candidate centers. For each center, we loop through all `n` darts to count how many are inside the circle. This results in a total time complexity of `O(n^2 * n) = O(n^3)`.Space: O(1) extra space, as we only need a few variables to store coordinates, distances, and counts.

Patterns

Math Geometry

Data structures

Array

Prompt

Alice is throwing n darts on a very large wall. You are given an array darts where darts[i] = [x_i, y_i] is the position of the i^th 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
-10⁴ <= x_i, y_i <= 10⁴
All the darts are unique
1 <= r <= 5000

Approaches

2 approaches with complexity analysis and trade-offs.

The fundamental insight for this approach is that an optimal circle (one containing the maximum number of darts) of a fixed radius r will, in general, have at least two of the darts on its boundary. If an optimal circle had fewer than two darts on its boundary, it could be moved without losing any enclosed darts until its boundary touched at least two darts. This allows us to drastically reduce the search space for the circle's center. Instead of checking an infinite number of possible centers, we only need to consider circles that are defined by pairs of darts.

Algorithm

Initialize maxDarts to 1, as a single dart can always be enclosed.
Iterate through every possible pair of darts, darts[i] and darts[j].
For each pair, calculate the distance d between them.
If d > 2 * r, no circle of radius r can contain both darts. Continue to the next pair.
If d <= 2 * r, there are two circles of radius r that pass through both darts[i] and darts[j]. We need to find their centers.
- Calculate the midpoint M of the line segment connecting the two darts.
- The distance from M to either center is h = sqrt(r^2 - (d/2)^2).
- The centers lie on the perpendicular bisector of the segment, at distance h from M. Calculate the coordinates of these two centers, C1 and C2.
For each center (C1 and C2):
- Initialize a counter to 0.
- Iterate through all n darts and check if their distance from the current center is less than or equal to r (with a small tolerance for floating-point errors).
- Increment the counter for each dart inside the circle.
Update maxDarts with the maximum count found so far.
After checking all pairs, return maxDarts.

Walkthrough

This method iterates through all unique pairs of darts. For each pair, it calculates the centers of the two possible circles of radius r that have both darts on their circumference. Then, for each of these two potential circles, it counts how many of the total darts fall within it. The maximum count found across all tested circles is the answer.

Here is the algorithm:

Initialize maxDarts to 1, as a single dart can always be enclosed.
Iterate through every possible pair of darts, darts[i] and darts[j].
For each pair, calculate the distance d between them.
If d > 2 * r, no circle of radius r can contain both darts. Continue to the next pair.
If d <= 2 * r, there are two circles of radius r that pass through both darts[i] and darts[j]. We need to find their centers.
- Calculate the midpoint M of the line segment connecting the two darts.
- The distance from M to either center is h = sqrt(r^2 - (d/2)^2).
- The centers lie on the perpendicular bisector of the segment, at distance h from M. Calculate the coordinates of these two centers, C1 and C2.
For each center (C1 and C2):
- Initialize a counter to 0.
- Iterate through all n darts and check if their distance from the current center is less than or equal to r (with a small tolerance for floating-point errors).
- Increment the counter for each dart inside the circle.
Update maxDarts with the maximum count found so far.
After checking all pairs, return maxDarts.

1class Solution {2    public int numPoints(int[][] darts, int r) {3        int n = darts.length;4        if (n <= 1) {5            return n;6        }7        int maxDarts = 1;8        double rDouble = (double) r;9 10        for (int i = 0; i < n; i++) {11            for (int j = i + 1; j < n; j++) {12                double x1 = darts[i][0], y1 = darts[i][1];13                double x2 = darts[j][0], y2 = darts[j][1];14 15                double distSq = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);16                17                if (distSq > 4 * rDouble * rDouble + 1e-9) {18                    continue;19                }20 21                double mx = (x1 + x2) / 2.0;22                double my = (y1 + y2) / 2.0;23                double dist = Math.sqrt(distSq);24                double h = Math.sqrt(Math.max(0.0, rDouble * rDouble - distSq / 4.0));25                26                double dx = x2 - x1;27                double dy = y2 - y1;28 29                double cx1 = mx + h * dy / dist;30                double cy1 = my - h * dx / dist;31                double cx2 = mx - h * dy / dist;32                double cy2 = my + h * dx / dist;33 34                int count1 = 0;35                for (int k = 0; k < n; k++) {36                    double px = darts[k][0], py = darts[k][1];37                    if ((px - cx1) * (px - cx1) + (py - cy1) * (py - cy1) <= rDouble * rDouble + 1e-9) {38                        count1++;39                    }40                }41                maxDarts = Math.max(maxDarts, count1);42 43                int count2 = 0;44                for (int k = 0; k < n; k++) {45                    double px = darts[k][0], py = darts[k][1];46                    if ((px - cx2) * (px - cx2) + (py - cy2) * (py - cy2) <= rDouble * rDouble + 1e-9) {47                        count2++;48                    }49                }50                maxDarts = Math.max(maxDarts, count2);51            }52        }53        return maxDarts;54    }55}

Complexity

Time

O(n^3). There are two nested loops to iterate through all `O(n^2)` pairs of darts. For each pair, we find two candidate centers. For each center, we loop through all `n` darts to count how many are inside the circle. This results in a total time complexity of `O(n^2 * n) = O(n^3)`.

Space

O(1) extra space, as we only need a few variables to store coordinates, distances, and counts.

Trade-offs

Pros

Relatively simple to understand and implement based on a clear geometric property.
Sufficiently efficient for the given constraints (n <= 100).

Cons

Its O(n^3) time complexity makes it less suitable for larger values of n.
Relies on floating-point arithmetic, which can introduce precision errors. A small epsilon value is needed for comparisons.

This approach refines the search by fixing one dart, say P_i, and assuming it lies on the boundary of the optimal circle. This assumption implies that the center of the optimal circle must lie on a circle of radius r centered at P_i. For every other dart P_j, we can determine the arc on this 'circle of centers' where any center would result in a dartboard that also contains P_j. By converting these arcs to angular intervals (events), we can use a radial sweep-line algorithm. The goal is to find the angle on the 'circle of centers' that is overlapped by the most arcs, as this corresponds to a center that covers the maximum number of darts.

Algorithm

Initialize maxDarts to 1.
Iterate through each dart P_i and treat it as a pivot point that must lie on the boundary of an optimal circle.
For each pivot P_i, the center of a potential optimal circle must lie on a 'circle of centers' of radius r around P_i.
For each other dart P_j:
- Calculate the distance d between P_i and P_j. If d > 2*r, P_j cannot be in the same circle, so we ignore it.
- Otherwise, P_j being inside the dartboard constrains the center to a specific arc on the 'circle of centers'.
- Calculate the angle alpha of the vector from P_i to P_j.
- Calculate the half-angle beta of the arc, where beta = acos(d / (2*r)).
- The angular interval for the center is [alpha - beta, alpha + beta].
- Create two events: a 'start' event at alpha - beta with type +1, and an 'end' event at alpha + beta with type -1.
After generating events for all P_j relative to P_i:
- Handle intervals that wrap around the -PI/PI boundary by keeping a separate wrappedCount.
- Sort all events by angle. When angles are equal, 'start' events (+1) should be processed before 'end' events (-1).
- Perform a radial sweep: Initialize a currentDarts counter (starting with wrappedCount) and iterate through the sorted events, updating the counter based on the event type. Track the maximum value of currentDarts seen during the sweep.
Update the global maxDarts with the maximum found for the pivot P_i.
Return maxDarts.

Walkthrough

For each dart, we consider it a pivot. We then calculate the angular range on a circle of radius r around this pivot where a center would cover each of the other darts. This transforms the problem into a 1D problem of finding the point on a circle's circumference covered by the most intervals. This is a classic application of the sweep-line algorithm.

Here is the algorithm:

Initialize maxDarts to 1.
Iterate through each dart P_i and treat it as a pivot point that must lie on the boundary of an optimal circle.
For each pivot P_i, the center of a potential optimal circle must lie on a 'circle of centers' of radius r around P_i.
For each other dart P_j:
- Calculate the distance d between P_i and P_j. If d > 2*r, P_j cannot be in the same circle, so we ignore it.
- Otherwise, P_j being inside the dartboard constrains the center to a specific arc on the 'circle of centers'.
- Calculate the angle alpha of the vector from P_i to P_j using atan2.
- Calculate the half-angle beta of the arc, where beta = acos(d / (2*r)).
- The angular interval for the center is [alpha - beta, alpha + beta].
- Create two events: a 'start' event at alpha - beta with type +1, and an 'end' event at alpha + beta with type -1.
After generating events for all P_j relative to P_i:
- Handle intervals that wrap around the -PI/PI boundary by keeping a separate wrappedCount.
- Sort all events by angle. When angles are equal, 'start' events (+1) should be processed before 'end' events (-1).
- Perform a radial sweep: Initialize a currentDarts counter (starting with wrappedCount) and iterate through the sorted events, updating the counter based on the event type. Track the maximum value of currentDarts seen during the sweep.
Update the global maxDarts with the maximum found for the pivot P_i.
Return maxDarts.

1import java.util.ArrayList;2import java.util.Collections;3import java.util.List;4 5class Solution {6    class Event implements Comparable<Event> {7        double angle;8        int type; // +1 for start, -1 for end9 10        Event(double angle, int type) {11            this.angle = angle;12            this.type = type;13        }14 15        @Override16        public int compareTo(Event other) {17            if (Math.abs(this.angle - other.angle) > 1e-9) {18                return Double.compare(this.angle, other.angle);19            }20            // Process +1 (start) before -1 (end)21            return Integer.compare(other.type, this.type);22        }23    }24 25    public int numPoints(int[][] darts, int r) {26        int n = darts.length;27        if (n <= 1) return n;28        int maxDarts = 1;29        double rDouble = (double) r;30 31        for (int i = 0; i < n; i++) {32            List<Event> events = new ArrayList<>();33            double px1 = darts[i][0], py1 = darts[i][1];34 35            for (int j = 0; j < n; j++) {36                if (i == j) continue;37 38                double px2 = darts[j][0], py2 = darts[j][1];39                double distSq = (px1 - px2) * (px1 - px2) + (py1 - py2) * (py1 - py2);40 41                if (distSq > 4 * rDouble * rDouble + 1e-9) {42                    continue;43                }44 45                double dist = Math.sqrt(distSq);46                double angleAlpha = Math.atan2(py2 - py1, px2 - px1);47                double angleBeta = Math.acos(dist / (2 * rDouble));48 49                double startAngle = angleAlpha - angleBeta;50                double endAngle = angleAlpha + angleBeta;51                52                events.add(new Event(startAngle, 1));53                events.add(new Event(endAngle, -1));54            }55 56            Collections.sort(events);57 58            int currentDarts = 1; // For the pivot point59            maxDarts = Math.max(maxDarts, currentDarts);60 61            for (Event e : events) {62                currentDarts += e.type;63                maxDarts = Math.max(maxDarts, currentDarts);64            }65        }66        return maxDarts;67    }68}

Complexity

Time

O(n^2 log n). The main loop iterates `n` times (once for each pivot dart). Inside the loop, we generate `O(n)` events for the other darts. Sorting these events takes `O(n log n)`. The final sweep takes `O(n)`. Therefore, the total complexity is `n * O(n log n) = O(n^2 log n)`.

Space

O(n) extra space, required to store the list of `O(n)` angular events for each pivot dart.

Trade-offs

Pros

More efficient with a time complexity of O(n^2 log n).
It's a standard and elegant computational geometry technique for solving this type of problem.

Cons

Significantly more complex to implement correctly, especially the handling of floating-point angles, normalization, and wrapped intervals.
Still relies on floating-point arithmetic and is susceptible to precision issues.

Solutions

Solution

1class Solution {2public3  int numPoints(int[][] points, int r) {4    int maxPoints = 1;5    int pointsCount = points.length;6    for (int i = 0; i < pointsCount; i++) {7      for (int j = i + 1; j < pointsCount; j++) {8        double[][] intersections = getIntersections(points[i], points[j], r);9        for (double[] intersection : intersections) {10          int pointsInCircle = 0;11          for (int[] point : points) {12            double distance = distance(intersection, point);13            if (distance <= r + 1 e - 5)14              pointsInCircle++;15          }16          maxPoints = Math.max(maxPoints, pointsInCircle);17        }18      }19    }20    return maxPoints;21  }22public23  double[][] getIntersections(int[] point1, int[] point2, int radius) {24    int squaredDistance = squaredDistance(point1, point2);25    if (squaredDistance > radius * radius * 4)26      return new double[0][2];27    else if (squaredDistance == radius * radius * 4) {28      double[] intersection = new double[2];29      for (int i = 0; i < 2; i++)30        intersection[i] = (point1[i] + point2[i]) / 2.0;31      double[][] intersections = new double[1][2];32      intersections[0] = intersection;33      return intersections;34    } else {35      double[] midPoint = new double[2];36      for (int i = 0; i < 2; i++)37        midPoint[i] = (point1[i] + point2[i]) / 2.0;38      double remaining = Math.sqrt(radius * radius - squaredDistance / 4.0);39      int difference1 = point1[1] - point2[1];40      int difference2 = point2[0] - point1[0];41      double radian = Math.atan(1.0 * difference2 / difference1);42      double[] intersection0 = {midPoint[0] + remaining * Math.cos(radian),43                                midPoint[1] + remaining * Math.sin(radian)};44      double[] intersection1 = {midPoint[0] - remaining * Math.cos(radian),45                                midPoint[1] - remaining * Math.sin(radian)};46      double[][] intersections = new double[2][2];47      intersections[0] = intersection0;48      intersections[1] = intersection1;49      return intersections;50    }51  }52public53  int squaredDistance(int[] point1, int[] point2) {54    return (point2[0] - point1[0]) * (point2[0] - point1[0]) +55           (point2[1] - point1[1]) * (point2[1] - point1[1]);56  }57public58  double distance(double[] point1, int[] point2) {59    return Math.sqrt((point2[0] - point1[0]) * (point2[0] - point1[0]) +60                     (point2[1] - point1[1]) * (point2[1] - point1[1]));61  }62}

1// OJ: https://leetcode.com/problems/maximum-number-of-darts-inside-of-a-circular-dartboard/ // Time: O(N^3) // Space: O(1) class Solution { inline double dist ( const vector < double > & a , const vector < double > & b ) { return sqrt ( pow ( a [ 0 ] - b [ 0 ], 2 ) + pow ( a [ 1 ] - b [ 1 ], 2 )); } vector < double > getPoint ( const vector < double > & a , const vector < double > & b , double p , double q ) { double x = ( a [ 1 ] - b [ 1 ] + b [ 0 ] * q - a [ 0 ] * p ) / ( q - p ); double y = a [ 1 ] + p * ( x - a [ 0 ]); return { x , y }; } vector < vector < double >> getCenters ( const vector < double > & a , const vector < double > & b , int r ) { double d = dist ( a , b ); if ( d > 2 * r ) return {}; if ( d == 2 * r ) return { { ( a [ 0 ] + b [ 0 ]) / 2 , ( a [ 1 ] + b [ 1 ]) / 2 } }; double theta = acos ( d / 2 / r ); double alpha = atan2 ( a [ 1 ] - b [ 1 ], a [ 0 ] - b [ 0 ]); double p = tan ( alpha + theta ), q = tan ( alpha - theta ); return { getPoint ( a , b , p , q ), getPoint ( a , b , q , p ) }; } public: int numPoints ( vector < vector < int >>& A , int r ) { int N = A . size (), ans = 0 ; for ( int i = 0 ; i < N ; ++ i ) { for ( int j = 0 ; j < N ; ++ j ) { for ( auto & center : getCenters ({( double ) A [ i ][ 0 ], ( double ) A [ i ][ 1 ]}, {( double ) A [ j ][ 0 ], ( double ) A [ j ][ 1 ]}, r )) { int cnt = 0 ; for ( auto & p : A ) { cnt += dist ( center , {( double ) p [ 0 ], ( double ) p [ 1 ]}) <= r + 0.00001 ; } ans = max ( ans , cnt ); } } } return ans ; } };

1class Solution:2    def numPoints(self, darts: list[list[int]], r: int) -> int: def countDarts(x, y): count = 0 for x1, y1 in darts: if dist((x, y), (x1, y1)) <= r + 1e-7: count += 1 return count def possibleCenters(x1, y1, x2, y2): dx, dy = x2 - x1, y2 - y1 d = sqrt(dx * dx + dy * dy) if d > 2 * r: return [] mid_x, mid_y = (x1 + x2) / 2, (y1 + y2) / 2 dist_to_center = sqrt(r * r - (d / 2) * (d / 2)) offset_x = dist_to_center * dy / d offset_y = dist_to_center * - dx / d return [(mid_x + offset_x, mid_y + offset_y), (mid_x - offset_x, mid_y - offset_y), ] n = len(darts) max_darts = 1 for i in range(n): for j in range(i + 1, n): centers = possibleCenters(darts[i][0], darts[i][1], darts[j][0], darts[j][1]) for center in centers: max_darts = max(max_darts, countDarts(center[0], center[1])) return max_darts

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem