Facebook Pixel

1453. Maximum Number of Darts Inside of a Circular Dartboard

HardGeometryArrayMath
Leetcode Link

Problem Description

Alice has thrown n darts at positions on a large wall. Each dart's position is given as coordinates [x_i, y_i] in the array darts.

Bob wants to place a circular dartboard with radius r somewhere on the wall to maximize the number of Alice's darts that fall within or on the boundary of the dartboard.

The task is to find the maximum number of darts that can be covered by optimally placing a dartboard of radius r.

Key Points:

  • You have n dart positions as 2D coordinates
  • You need to place a circle of radius r to cover as many darts as possible
  • A dart is covered if it lies inside or exactly on the boundary of the circle
  • Return the maximum number of darts that can be covered

Example: If you have darts at positions [[1,2], [3,4], [5,6]] and radius r = 2, you need to find where to place a circle of radius 2 to cover the maximum number of these dart positions.

The solution approach involves:

  1. For each pair of darts, calculate potential circle centers where a circle of radius r passes through both darts
  2. For each potential center, count how many total darts fall within radius r
  3. Track the maximum count found

The geometric insight is that an optimal circle placement will have at least two darts on its boundary (unless only one dart can be covered). This is why the solution examines all pairs of darts to find candidate circle centers.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The key insight is that if we want to maximize the number of darts covered by a circle, the optimal placement will often have the circle's boundary passing through at least one or two darts. Why? Because if a circle covers some darts but none of them touch its boundary, we could slightly shift the circle to potentially include more darts.

Think about it this way: if we have an optimal circle placement, we can keep moving it until at least two darts are on its boundary. This movement won't reduce the number of covered darts (since we're not pushing any darts outside), and it might even allow us to include more.

This observation drastically reduces our search space. Instead of considering infinite possible positions for the circle center, we only need to consider positions where the circle passes through pairs of darts.

For any two darts within distance 2r of each other (if they're farther apart, no circle of radius r can contain both), there are exactly two possible positions for a circle center such that both darts lie on the circle's boundary. These two positions are found by:

  1. Finding the midpoint between the two darts
  2. Moving perpendicular to the line connecting the darts by a specific distance

The perpendicular distance is calculated using the Pythagorean theorem: if the distance between two darts is d, and they both lie on a circle of radius r, then the center is at distance sqrt(r² - (d/2)²) from the midpoint, perpendicular to the line connecting the darts.

By checking all pairs of darts and their corresponding possible circle centers, we ensure we don't miss the optimal placement. For each candidate center, we count how many darts fall within radius r and keep track of the maximum count.

The algorithm handles the edge case where only one dart can be covered by initializing the maximum to 1, and the floating-point comparison uses a small epsilon (1e-7) to handle numerical precision issues.

Learn more about Math patterns.

Solution Approach

The implementation consists of three main components:

1. Finding Possible Circle Centers (possibleCenters function)

For two darts at positions (x1, y1) and (x2, y2), we calculate where a circle of radius r can be centered such that both darts lie on its boundary:

  • First, calculate the distance d between the two darts: d = sqrt((x2-x1)² + (y2-y1)²)
  • If d > 2r, no circle of radius r can contain both darts, return empty list
  • Find the midpoint: (mid_x, mid_y) = ((x1+x2)/2, (y1+y2)/2)
  • Calculate the perpendicular distance from midpoint to center: dist_to_center = sqrt(r² - (d/2)²)
  • The perpendicular direction is obtained by rotating the vector (dx, dy) by 90 degrees: (dy, -dx)
  • Normalize and scale this perpendicular vector to get the offset:
    • offset_x = dist_to_center * dy / d
    • offset_y = dist_to_center * -dx / d
  • Return two possible centers: one on each side of the line connecting the darts

2. Counting Darts Within Circle (countDarts function)

For a given center (x, y), count how many darts fall within or on the circle:

  • Iterate through all darts
  • Calculate distance from each dart to the center using the distance formula
  • If distance ≤ r + 1e-7, increment the count (the small epsilon handles floating-point precision)

3. Main Algorithm

The main algorithm exhaustively checks all possible optimal placements:

max_darts = 1  # At least one dart can always be covered
for i in range(n):
    for j in range(i + 1, n):
        # Get possible centers where circle passes through darts i and j
        centers = possibleCenters(darts[i], darts[j])
      
        # For each center, count darts and update maximum
        for center in centers:
            max_darts = max(max_darts, countDarts(center))

Time Complexity: O(n² × n) = O(n³) where n is the number of darts

  • We check O(n²) pairs of darts
  • For each pair, we generate at most 2 centers
  • For each center, we count darts in O(n) time

Space Complexity: O(1) as we only use a constant amount of extra space regardless of input size

The algorithm guarantees finding the optimal solution because it checks all geometrically significant positions where the circle boundary passes through pairs of darts, which includes all potential optimal placements.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a concrete example with darts at positions [[1,2], [3,2], [2,4]] and radius r = 2.

Step 1: Initialize

  • Start with max_darts = 1 (we can always cover at least one dart)

Step 2: Check all pairs of darts

Pair 1: Darts [1,2] and [3,2]

  • Distance between them: d = sqrt((3-1)² + (2-2)²) = 2
  • Since d = 2 ≤ 2r = 4, we can find circle centers
  • Midpoint: (2, 2)
  • Perpendicular distance: sqrt(4 - 1) = sqrt(3) ≈ 1.732
  • The line between darts is horizontal, so perpendicular is vertical
  • Two possible centers: (2, 2+1.732) and (2, 2-1.732)
    • Center at (2, 3.732): Check distances to all darts
      • Dart [1,2]: sqrt((1-2)² + (2-3.732)²) = sqrt(1 + 3) = 2 ✓ (on boundary)
      • Dart [3,2]: sqrt((3-2)² + (2-3.732)²) = sqrt(1 + 3) = 2 ✓ (on boundary)
      • Dart [2,4]: sqrt((2-2)² + (4-3.732)²) = 0.268 < 2 ✓ (inside)
      • Count: 3 darts
    • Center at (2, 0.268): Would only cover the first two darts

Pair 2: Darts [1,2] and [2,4]

  • Distance: d = sqrt(1 + 4) = sqrt(5) ≈ 2.236
  • Since d ≤ 4, find centers
  • Midpoint: (1.5, 3)
  • Perpendicular distance: sqrt(4 - 1.25) ≈ 1.658
  • Calculate two centers and count covered darts
    • Best count from this pair: 2 darts

Pair 3: Darts [3,2] and [2,4]

  • Distance: d = sqrt(1 + 4) = sqrt(5) ≈ 2.236
  • Similar process yields at most 2 darts covered

Step 3: Return maximum

  • The maximum count found is 3 darts, achieved when the circle is centered at approximately (2, 3.732)

This example demonstrates how the algorithm systematically checks all pairs of darts to find circle placements where two darts lie on the boundary, then counts all darts within each such circle to find the optimal placement.

Solution Implementation

1class Solution:
2    def numPoints(self, darts: list[list[int]], r: int) -> int:
3        """
4        Find the maximum number of darts that can be enclosed within a dartboard of radius r.
5      
6        The algorithm works by finding all possible circle centers that pass through pairs of darts,
7        then counting how many darts fall within each circle.
8      
9        Args:
10            darts: List of [x, y] coordinates representing dart positions
11            r: Radius of the dartboard
12          
13        Returns:
14            Maximum number of darts that can be enclosed in a circle of radius r
15        """
16        from math import sqrt
17      
18        def count_darts_in_circle(center_x: float, center_y: float) -> int:
19            """
20            Count how many darts are within the circle centered at (center_x, center_y).
21          
22            Args:
23                center_x: X-coordinate of circle center
24                center_y: Y-coordinate of circle center
25              
26            Returns:
27                Number of darts within the circle (including boundary)
28            """
29            count = 0
30            for dart_x, dart_y in darts:
31                # Calculate distance from dart to center
32                distance = sqrt((center_x - dart_x) ** 2 + (center_y - dart_y) ** 2)
33                # Check if dart is within circle (with small epsilon for floating point comparison)
34                if distance <= r + 1e-7:
35                    count += 1
36            return count
37      
38        def find_circle_centers(x1: float, y1: float, x2: float, y2: float) -> list[tuple[float, float]]:
39            """
40            Find the two possible centers of circles with radius r that pass through 
41            points (x1, y1) and (x2, y2).
42          
43            Args:
44                x1, y1: Coordinates of first point
45                x2, y2: Coordinates of second point
46              
47            Returns:
48                List of up to 2 possible circle centers as (x, y) tuples
49            """
50            # Calculate distance between the two points
51            dx = x2 - x1
52            dy = y2 - y1
53            distance_between_points = sqrt(dx * dx + dy * dy)
54          
55            # If points are too far apart, no circle of radius r can pass through both
56            if distance_between_points > 2 * r:
57                return []
58          
59            # Find midpoint between the two points
60            mid_x = (x1 + x2) / 2
61            mid_y = (y1 + y2) / 2
62          
63            # Calculate distance from midpoint to circle center
64            # Using Pythagorean theorem: r^2 = (d/2)^2 + dist_to_center^2
65            dist_to_center = sqrt(r * r - (distance_between_points / 2) * (distance_between_points / 2))
66          
67            # Calculate perpendicular offset from midpoint to circle centers
68            # The perpendicular direction is obtained by rotating the vector (dx, dy) by 90 degrees
69            offset_x = dist_to_center * dy / distance_between_points
70            offset_y = dist_to_center * (-dx) / distance_between_points
71          
72            # Return both possible circle centers
73            return [
74                (mid_x + offset_x, mid_y + offset_y),
75                (mid_x - offset_x, mid_y - offset_y),
76            ]
77      
78        n = len(darts)
79        max_darts_in_circle = 1  # At minimum, we can always enclose one dart
80      
81        # Try all pairs of darts to find circle centers
82        for i in range(n):
83            for j in range(i + 1, n):
84                # Find possible circle centers that pass through darts[i] and darts[j]
85                possible_centers = find_circle_centers(
86                    darts[i][0], darts[i][1], 
87                    darts[j][0], darts[j][1]
88                )
89              
90                # For each possible center, count darts and update maximum
91                for center_x, center_y in possible_centers:
92                    darts_count = count_darts_in_circle(center_x, center_y)
93                    max_darts_in_circle = max(max_darts_in_circle, darts_count)
94      
95        return max_darts_in_circle
96
1class Solution {
2    /**
3     * Finds the maximum number of darts that can be enclosed within a circle of radius r.
4     * Uses the property that the optimal circle must pass through at least two dart points.
5     * 
6     * @param darts 2D array where each element represents [x, y] coordinates of a dart
7     * @param r radius of the circle
8     * @return maximum number of darts that can be enclosed
9     */
10    public int numPoints(int[][] darts, int r) {
11        int n = darts.length;
12        int maxDarts = 1; // At minimum, we can always enclose one dart
13      
14        // Try all pairs of darts as potential points on the circle boundary
15        for (int i = 0; i < n; i++) {
16            for (int j = i + 1; j < n; j++) {
17                // Find possible circle centers that pass through both darts[i] and darts[j]
18                List<double[]> centers = possibleCenters(
19                    darts[i][0], darts[i][1], 
20                    darts[j][0], darts[j][1], 
21                    r
22                );
23              
24                // For each possible center, count how many darts it can enclose
25                for (double[] center : centers) {
26                    maxDarts = Math.max(maxDarts, countDarts(center[0], center[1], darts, r));
27                }
28            }
29        }
30      
31        return maxDarts;
32    }
33  
34    /**
35     * Calculates possible circle centers with radius r that pass through two given points.
36     * There can be 0, 1, or 2 such centers depending on the distance between points.
37     * 
38     * @param x1, y1 coordinates of first point
39     * @param x2, y2 coordinates of second point
40     * @param r radius of the circle
41     * @return list of possible center coordinates [x, y]
42     */
43    private List<double[]> possibleCenters(int x1, int y1, int x2, int y2, int r) {
44        List<double[]> centers = new ArrayList<>();
45      
46        // Calculate distance between the two points
47        double dx = x2 - x1;
48        double dy = y2 - y1;
49        double distance = Math.sqrt(dx * dx + dy * dy);
50      
51        // If points are too far apart, no circle of radius r can pass through both
52        if (distance > 2 * r) {
53            return centers;
54        }
55      
56        // Find midpoint between the two points
57        double midX = (x1 + x2) / 2.0;
58        double midY = (y1 + y2) / 2.0;
59      
60        // Calculate perpendicular distance from midpoint to circle center
61        // Using Pythagorean theorem: r² = (d/2)² + distToCenter²
62        double distToCenter = Math.sqrt(r * r - (distance / 2.0) * (distance / 2.0));
63      
64        // Calculate perpendicular offset direction (rotated 90 degrees)
65        // Perpendicular vector to (dx, dy) is (-dy, dx) or (dy, -dx)
66        double offsetX = distToCenter * dy / distance;
67        double offsetY = distToCenter * (-dx) / distance;
68      
69        // Two possible centers: one on each side of the line connecting the points
70        centers.add(new double[] {midX + offsetX, midY + offsetY});
71        centers.add(new double[] {midX - offsetX, midY - offsetY});
72      
73        return centers;
74    }
75  
76    /**
77     * Counts how many darts are within or on the boundary of a circle.
78     * 
79     * @param x, y coordinates of the circle center
80     * @param darts array of dart coordinates
81     * @param r radius of the circle
82     * @return number of darts enclosed by the circle
83     */
84    private int countDarts(double x, double y, int[][] darts, int r) {
85        int count = 0;
86        double epsilon = 1e-7; // Small tolerance for floating-point comparison
87      
88        for (int[] dart : darts) {
89            // Calculate distance from dart to circle center
90            double distance = Math.sqrt(
91                Math.pow(dart[0] - x, 2) + Math.pow(dart[1] - y, 2)
92            );
93          
94            // Check if dart is within or on the circle boundary (with tolerance)
95            if (distance <= r + epsilon) {
96                count++;
97            }
98        }
99      
100        return count;
101    }
102}
103
1class Solution {
2public:
3    /**
4     * Finds the maximum number of darts that can be enclosed within a circle of radius r.
5     * Uses the property that the optimal circle must pass through at least two dart points.
6     * 
7     * @param darts 2D vector where each element represents [x, y] coordinates of a dart
8     * @param r radius of the circle
9     * @return maximum number of darts that can be enclosed
10     */
11    int numPoints(vector<vector<int>>& darts, int r) {
12        int n = darts.size();
13        int maxDarts = 1; // At minimum, we can always enclose one dart
14      
15        // Try all pairs of darts as potential points on the circle boundary
16        for (int i = 0; i < n; i++) {
17            for (int j = i + 1; j < n; j++) {
18                // Find possible circle centers that pass through both darts[i] and darts[j]
19                vector<pair<double, double>> centers = possibleCenters(
20                    darts[i][0], darts[i][1], 
21                    darts[j][0], darts[j][1], 
22                    r
23                );
24              
25                // For each possible center, count how many darts it can enclose
26                for (const auto& center : centers) {
27                    maxDarts = max(maxDarts, countDarts(center.first, center.second, darts, r));
28                }
29            }
30        }
31      
32        return maxDarts;
33    }
34  
35private:
36    /**
37     * Calculates possible circle centers with radius r that pass through two given points.
38     * There can be 0, 1, or 2 such centers depending on the distance between points.
39     * 
40     * @param x1, y1 coordinates of first point
41     * @param x2, y2 coordinates of second point
42     * @param r radius of the circle
43     * @return vector of possible center coordinates as pairs (x, y)
44     */
45    vector<pair<double, double>> possibleCenters(int x1, int y1, int x2, int y2, int r) {
46        vector<pair<double, double>> centers;
47      
48        // Calculate distance between the two points
49        double dx = x2 - x1;
50        double dy = y2 - y1;
51        double distance = sqrt(dx * dx + dy * dy);
52      
53        // If points are too far apart, no circle of radius r can pass through both
54        if (distance > 2 * r) {
55            return centers;
56        }
57      
58        // Find midpoint between the two points
59        double midX = (x1 + x2) / 2.0;
60        double midY = (y1 + y2) / 2.0;
61      
62        // Special case: if points are the same, return the point itself as center
63        if (distance < 1e-7) {
64            centers.push_back({static_cast<double>(x1), static_cast<double>(y1)});
65            return centers;
66        }
67      
68        // Calculate perpendicular distance from midpoint to circle center
69        // Using Pythagorean theorem: r² = (d/2)² + distToCenter²
70        double distToCenter = sqrt(r * r - (distance / 2.0) * (distance / 2.0));
71      
72        // Calculate perpendicular offset direction (rotated 90 degrees)
73        // Perpendicular vector to (dx, dy) is (-dy, dx) or (dy, -dx)
74        double offsetX = distToCenter * dy / distance;
75        double offsetY = distToCenter * (-dx) / distance;
76      
77        // Two possible centers: one on each side of the line connecting the points
78        centers.push_back({midX + offsetX, midY + offsetY});
79        centers.push_back({midX - offsetX, midY - offsetY});
80      
81        return centers;
82    }
83  
84    /**
85     * Counts how many darts are within or on the boundary of a circle.
86     * 
87     * @param x, y coordinates of the circle center
88     * @param darts vector of dart coordinates
89     * @param r radius of the circle
90     * @return number of darts enclosed by the circle
91     */
92    int countDarts(double x, double y, const vector<vector<int>>& darts, int r) {
93        int count = 0;
94        double epsilon = 1e-7; // Small tolerance for floating-point comparison
95      
96        for (const auto& dart : darts) {
97            // Calculate distance from dart to circle center
98            double distance = sqrt(
99                pow(dart[0] - x, 2) + pow(dart[1] - y, 2)
100            );
101          
102            // Check if dart is within or on the circle boundary (with tolerance)
103            if (distance <= r + epsilon) {
104                count++;
105            }
106        }
107      
108        return count;
109    }
110};
111
1/**
2 * Finds the maximum number of darts that can be enclosed within a circle of radius r.
3 * Uses the property that the optimal circle must pass through at least two dart points.
4 * 
5 * @param darts 2D array where each element represents [x, y] coordinates of a dart
6 * @param r radius of the circle
7 * @return maximum number of darts that can be enclosed
8 */
9function numPoints(darts: number[][], r: number): number {
10    const n = darts.length;
11    let maxDarts = 1; // At minimum, we can always enclose one dart
12  
13    // Try all pairs of darts as potential points on the circle boundary
14    for (let i = 0; i < n; i++) {
15        for (let j = i + 1; j < n; j++) {
16            // Find possible circle centers that pass through both darts[i] and darts[j]
17            const centers = possibleCenters(
18                darts[i][0], darts[i][1], 
19                darts[j][0], darts[j][1], 
20                r
21            );
22          
23            // For each possible center, count how many darts it can enclose
24            for (const center of centers) {
25                maxDarts = Math.max(maxDarts, countDarts(center[0], center[1], darts, r));
26            }
27        }
28    }
29  
30    return maxDarts;
31}
32
33/**
34 * Calculates possible circle centers with radius r that pass through two given points.
35 * There can be 0, 1, or 2 such centers depending on the distance between points.
36 * 
37 * @param x1 x-coordinate of first point
38 * @param y1 y-coordinate of first point
39 * @param x2 x-coordinate of second point
40 * @param y2 y-coordinate of second point
41 * @param r radius of the circle
42 * @return array of possible center coordinates [x, y]
43 */
44function possibleCenters(x1: number, y1: number, x2: number, y2: number, r: number): number[][] {
45    const centers: number[][] = [];
46  
47    // Calculate distance between the two points
48    const dx = x2 - x1;
49    const dy = y2 - y1;
50    const distance = Math.sqrt(dx * dx + dy * dy);
51  
52    // If points are too far apart, no circle of radius r can pass through both
53    if (distance > 2 * r) {
54        return centers;
55    }
56  
57    // Find midpoint between the two points
58    const midX = (x1 + x2) / 2.0;
59    const midY = (y1 + y2) / 2.0;
60  
61    // Special case: if two points are the same, return the point as center
62    if (distance === 0) {
63        centers.push([midX, midY]);
64        return centers;
65    }
66  
67    // Calculate perpendicular distance from midpoint to circle center
68    // Using Pythagorean theorem: r² = (d/2)² + distToCenter²
69    const distToCenter = Math.sqrt(r * r - (distance / 2.0) * (distance / 2.0));
70  
71    // Calculate perpendicular offset direction (rotated 90 degrees)
72    // Perpendicular vector to (dx, dy) is (-dy, dx) or (dy, -dx)
73    const offsetX = distToCenter * dy / distance;
74    const offsetY = distToCenter * (-dx) / distance;
75  
76    // Two possible centers: one on each side of the line connecting the points
77    centers.push([midX + offsetX, midY + offsetY]);
78    centers.push([midX - offsetX, midY - offsetY]);
79  
80    return centers;
81}
82
83/**
84 * Counts how many darts are within or on the boundary of a circle.
85 * 
86 * @param x x-coordinate of the circle center
87 * @param y y-coordinate of the circle center
88 * @param darts array of dart coordinates
89 * @param r radius of the circle
90 * @return number of darts enclosed by the circle
91 */
92function countDarts(x: number, y: number, darts: number[][], r: number): number {
93    let count = 0;
94    const epsilon = 1e-7; // Small tolerance for floating-point comparison
95  
96    for (const dart of darts) {
97        // Calculate distance from dart to circle center
98        const distance = Math.sqrt(
99            Math.pow(dart[0] - x, 2) + Math.pow(dart[1] - y, 2)
100        );
101      
102        // Check if dart is within or on the circle boundary (with tolerance)
103        if (distance <= r + epsilon) {
104            count++;
105        }
106    }
107  
108    return count;
109}
110

Time and Space Complexity

Time Complexity: O(n³) where n is the number of darts.

The analysis breaks down as follows:

  • The outer two nested loops iterate through all pairs of darts: O(n²) pairs in total
  • For each pair of darts, possibleCenters computes at most 2 circle centers in O(1) time
  • For each center (at most 2 per pair), countDarts is called, which iterates through all n darts to count how many fall within the radius: O(n) time
  • Overall: O(n²) × O(1) × 2 × O(n) = O(n³)

Space Complexity: O(1)

The space analysis:

  • The possibleCenters function creates a list with at most 2 coordinate pairs: O(1)
  • The countDarts function uses only a counter variable: O(1)
  • No recursive calls or data structures that scale with input size
  • Only a constant amount of variables (max_darts, centers, loop indices, temporary calculations) are used
  • Overall auxiliary space: O(1)

Note: The input array darts is not counted in space complexity as it's part of the input.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Floating-Point Precision Errors

The Problem: When checking if a dart is within the circle, direct floating-point comparison can fail due to precision errors. A dart that should be exactly on the boundary might be calculated as slightly outside due to accumulated floating-point arithmetic errors.

# Problematic code:
if distance <= r:  # May incorrectly exclude boundary points
    count += 1

The Solution: Add a small epsilon value to account for floating-point imprecision:

# Correct approach:
if distance <= r + 1e-7:  # Small epsilon handles precision issues
    count += 1

2. Division by Zero When Points Coincide

The Problem: When two darts are at the exact same position (distance = 0), the normalization step divides by zero:

# This causes division by zero when distance_between_points = 0:
offset_x = dist_to_center * dy / distance_between_points
offset_y = dist_to_center * (-dx) / distance_between_points

The Solution: Check for coincident points before calculating centers:

def find_circle_centers(x1, y1, x2, y2):
    dx = x2 - x1
    dy = y2 - y1
    distance_between_points = sqrt(dx * dx + dy * dy)
  
    # Handle coincident points
    if distance_between_points < 1e-9:
        # Return the point itself as the only center
        return [(x1, y1)]
  
    # Continue with normal calculation...
    if distance_between_points > 2 * r:
        return []

3. Missing Edge Case: Single Dart Coverage

The Problem: The algorithm only checks circles passing through pairs of darts, but might miss the optimal placement when the best solution is a circle centered directly on a single dart (with no other darts on the boundary).

The Solution: Additionally check circles centered at each dart position:

# Add this to the main algorithm:
for i in range(n):
    # Check circle centered at dart i
    count = count_darts_in_circle(darts[i][0], darts[i][1])
    max_darts_in_circle = max(max_darts_in_circle, count)

4. Numerical Instability in Square Root Calculation

The Problem: When two points are very close to being exactly 2r apart, the expression r * r - (distance_between_points / 2) * (distance_between_points / 2) can become slightly negative due to floating-point errors, causing sqrt() to fail.

The Solution: Clamp the value to ensure it's non-negative:

# Instead of:
dist_to_center = sqrt(r * r - (distance_between_points / 2) * (distance_between_points / 2))

# Use:
squared_dist = r * r - (distance_between_points / 2) * (distance_between_points / 2)
dist_to_center = sqrt(max(0, squared_dist))  # Clamp to non-negative

5. Not Handling the Case Where All Darts Are Far Apart

The Problem: When all darts are more than 2r apart from each other, no pair will generate valid circle centers, but the algorithm should still return 1 (covering at least one dart).

The Solution: Initialize max_darts_in_circle = 1 at the start, which handles this case automatically, or explicitly check circles centered at each individual dart as mentioned in pitfall #3.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

A heap is a ...?

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More