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.

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}

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