Maximum Number of Darts Inside of a Circular Dartboard - Problem

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 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.

Note: A dart is considered to be on the dartboard if the distance from the center of the dartboard to the dart is at most r.

Input & Output

Example 1 — Basic Case

$ Input: darts = [[-2,0],[2,0],[0,2],[0,-2]], r = 2

› Output: 4

💡 Note: Circle centered at (0,0) with radius 2 can cover all 4 darts positioned at distance 2 from origin

Example 2 — Partial Coverage

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

› Output: 5

💡 Note: Optimal circle placement can cover at most 5 out of 6 darts given the radius constraint

Example 3 — Single Dart

$ Input: darts = [[1,2]], r = 1

› Output: 1

💡 Note: With only one dart, any circle of radius 1 containing that dart covers exactly 1 dart

Constraints

1 ≤ darts.length ≤ 100
darts[i].length == 2
-10⁴ ≤ x_i, y_i ≤ 10⁴
1 ≤ r ≤ 5000

Visualization

Tap to expand

Asked in

G Google 15 M Microsoft 12 A Apple 8

The key insight is that the optimal circle either contains ≤1 dart or passes through 2+ darts on its boundary. We can find optimal centers by considering all pairs of darts and calculating possible circle centers of radius r through both points. Best approach is the geometric method with Time: O(n³), Space: O(1).

Common Approaches

✓ Brute Force - Try All Positions

⏱️ Time: O(n²) Space: O(1)

For each dart position as potential circle center, count how many darts fall within radius r. This gives a reasonable approximation but may miss optimal positions between darts.

Geometric Approach - Circle Through Two Points

⏱️ Time: O(n³) Space: O(1)

The optimal circle either contains ≤1 dart or passes through 2+ darts on its boundary. For each pair of darts, find the two possible circle centers of radius r that pass through both points, then count enclosed darts.

Brute Force - Try All Positions — Algorithm Steps

Step 1: For each dart position, use it as circle center
Step 2: Count all darts within distance r from this center
Step 3: Return maximum count found

Visualization

Tap to expand

Step-by-Step Walkthrough

Try First Dart

Place circle center at first dart, count enclosed darts

Try Next Dart

Move circle center to next dart position

Best Result

Return maximum count found across all positions

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int solution(int darts[][2], int n, int r) {
    if (n == 1) return 1;
    
    int maxCount = 1;
    
    // Try each dart position as circle center
    for (int i = 0; i < n; i++) {
        int cx = darts[i][0];
        int cy = darts[i][1];
        int count = 0;
        
        // Count darts within radius r
        for (int j = 0; j < n; j++) {
            double dx = darts[j][0] - cx;
            double dy = darts[j][1] - cy;
            if (dx * dx + dy * dy <= (double)r * r + 1e-7) {
                count++;
            }
        }
        
        if (count > maxCount) {
            maxCount = count;
        }
    }
    
    return maxCount;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int darts[100][2];
    int n = 0;
    
    // Simple parsing of [[x1,y1],[x2,y2],...]
    char* ptr = line + 1; // Skip first [
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            darts[n][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++; // Skip comma
            darts[n][1] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            n++;
        }
        ptr++;
    }
    
    int r;
    scanf("%d", &r);
    
    printf("%d\n", solution(darts, n, r));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n darts, we check distance to all n darts

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables for counting and distance calculations

✓ Linear Space

12.5K Views

Medium Frequency

~35 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Maximum Number of Darts Inside of a Circular Dartboard - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Positions — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler