Maximum Number of Darts Inside of a Circular Dartboard

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

Understanding the Visualization

Input

Given dart positions and circle radius r

Process

Find optimal circle placement to maximize coverage

Output

Return maximum number of darts that can be covered

Key Takeaway

🎯 Key Insight: The optimal circle passes through at least 2 darts on its boundary, reducing infinite possibilities to finite geometric calculations

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

Approach	Time	Space	Notes
✓ Brute Force - Try All Positions	O(n²)	O(1)	Try placing circle center at every dart position and count enclosed darts
Geometric Approach - Circle Through Two Points	O(n³)	O(1)	Find all possible circle centers that pass through pairs of darts on the boundary

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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Positions — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler