Jobs

Interviews

Discussions

Maximum Number of Darts Inside of a Circular Dartboard

Hard

Asked by:

14 views

Topics:

Arrays

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

Try coding it in LeetCode

Maximum Number of Darts Inside of a Circular Dartboard

Hard

Asked by:

14 views

Topics:

Arrays

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the data type for the coordinates of the points and the radius? Can they be floats or just integers?
What are the constraints on the number of points? Is there a maximum value for the number of points?
Is the center of the circle fixed or can I choose any point as the center?
If no points can be inside a circle of given radius, what should the function return? Should I return 0?
Are there any edge cases I should be aware of, such as points coinciding with each other or the circle's edge?

Brute Force Solution

Approach

The brute force approach to this dartboard problem involves checking every possible circle location and seeing how many darts fall inside. We essentially try out all combinations to find the circle that captures the most darts. It's like drawing a circle on the dartboard over and over, each time in a slightly different spot, and counting the darts inside.

Here's how the algorithm would work step-by-step:

First, consider every possible pair of darts as the center of a potential circle.
For each of these potential circle centers, check if all the other darts are within the specified radius of that center.
Count how many darts are inside (or on the edge) of each circle you check.
Remember the maximum number of darts you found inside any of the circles.
After checking all possible circle center positions, the largest count you remember is the answer: the maximum number of darts inside a circle.

Code Implementation

def max_darts_inside(darts, radius):
    max_darts = 0
    number_of_darts = len(darts)

    for i in range(number_of_darts):
        for j in range(i + 1, number_of_darts):
            # Consider each pair of darts as potential circle centers.

            center_x = (darts[i][0] + darts[j][0]) / 2
            center_y = (darts[i][1] + darts[j][1]) / 2

            darts_inside = 0

            for k in range(number_of_darts):
                distance = ((darts[k][0] - center_x) ** 2 + (darts[k][1] - center_y) ** 2) ** 0.5

                # Count the darts within the radius of the center
                if distance <= radius:
                    darts_inside += 1

            max_darts = max(max_darts, darts_inside)

    # Check each dart as a potential center point.
    for i in range(number_of_darts):
        center_x = darts[i][0]
        center_y = darts[i][1]
        darts_inside = 0

        for j in range(number_of_darts):
            distance = ((darts[j][0] - center_x) ** 2 + (darts[j][1] - center_y) ** 2) ** 0.5

            if distance <= radius:
                darts_inside += 1

        max_darts = max(max_darts, darts_inside)

    # Return the maximum number of darts within any circle
    return max_darts

Big(O) Analysis

Time Complexity

O(n³) – The algorithm considers every pair of darts (n * (n-1) / 2 which is O(n²)) as potential circle centers. For each potential center, it iterates through all n darts to check if they lie within the radius. Therefore, the total number of operations is approximately (n² * n), which simplifies to O(n³).

Space Complexity

O(1) – The described brute force approach iterates through pairs of darts and counts darts within a circle centered at each pair. It primarily uses a few variables to store the current maximum count and loop indices. No auxiliary data structures that scale with the number of darts, N, are utilized for storing intermediate dart positions or circle configurations. Therefore, the auxiliary space complexity remains constant regardless of the number of darts, resulting in O(1) space complexity.

Optimal Solution

Approach

The key idea is to try all possible pairs of points as potential centers of circles and count how many other points fall within a circle of the given radius centered at each candidate. By systematically checking pairs, we avoid examining every possible combination of three or more points to define a circle.

Here's how the algorithm would work step-by-step:

Consider all possible pairs of points from the given list. Each pair represents two points that could lie on the circumference of the circular dartboard.
For each pair of points, calculate the center of the possible circle passing through those two points.
Iterate through *all* the points in the given list, and for each point, check if it falls inside the circle centered at the calculated center. A point is considered inside the circle if the distance between the point and the center is less than or equal to the given radius.
Keep track of the largest number of points that fall within any of the tested circles. This maximum value is the answer.
Since each pair of points is treated as a potential base for a circle, and all other points are then checked for being inside that circle, the algorithm effectively finds the best possible circle placement for containing the most points.

Code Implementation

import math

def maximum_number_of_darts_inside(points, radius):
    number_of_points = len(points)
    if number_of_points <= 1:
        return number_of_points

    max_points_inside = 1

    for i in range(number_of_points):
        for j in range(i + 1, number_of_points):
            point1_x, point1_y = points[i]
            point2_x, point2_y = points[j]

            # Calculate the distance between the two points.
            distance_between_points = math.sqrt((point1_x - point2_x)**2 + (point1_y - point2_y)**2)

            # If the distance is greater than 2 * radius, skip.
            if distance_between_points > 2 * radius:
                continue

            # Calculate the midpoint between the two points.
            midpoint_x = (point1_x + point2_x) / 2
            midpoint_y = (point1_y + point2_y) / 2

            # Calculate the distance from midpoint to center.
            distance_to_center = math.sqrt(radius**2 - (distance_between_points / 2)**2)

            # Calculate the center 1.
            center1_x = midpoint_x + distance_to_center * (point1_y - point2_y) / distance_between_points
            center1_y = midpoint_y + distance_to_center * (point2_x - point1_x) / distance_between_points

            # Count the number of points inside the circle with center 1.
            points_inside_center1 = 0
            for k in range(number_of_points):
                point_x, point_y = points[k]
                distance_to_center1 = math.sqrt((point_x - center1_x)**2 + (point_y - center1_y)**2)
                if distance_to_center1 <= radius:
                    points_inside_center1 += 1

            max_points_inside = max(max_points_inside, points_inside_center1)

            # Calculate the center 2.
            center2_x = midpoint_x - distance_to_center * (point1_y - point2_y) / distance_between_points
            center2_y = midpoint_y - distance_to_center * (point2_x - point1_x) / distance_between_points

            # Count the number of points inside the circle with center 2.
            points_inside_center2 = 0
            for k in range(number_of_points):
                point_x, point_y = points[k]
                distance_to_center2 = math.sqrt((point_x - center2_x)**2 + (point_y - center2_y)**2)
                if distance_to_center2 <= radius:
                    points_inside_center2 += 1

            max_points_inside = max(max_points_inside, points_inside_center2)

    # Iterate through all points as possible centers
    for i in range(number_of_points):
        point_x, point_y = points[i]
        points_inside = 0
        # Check all other points if they fall within radius
        for j in range(number_of_points):
            other_point_x, other_point_y = points[j]
            distance = math.sqrt((point_x - other_point_x)**2 + (point_y - other_point_y)**2)
            if distance <= radius:
                points_inside += 1

        # Update the max points inside the circle
        max_points_inside = max(max_points_inside, points_inside)

    return max_points_inside

Big(O) Analysis

Time Complexity

O(n^3) – The algorithm iterates through all possible pairs of points, which contributes O(n^2) because we're choosing 2 points from n. For each pair, it computes a potential circle center. Then, it iterates through *all* n points to check if they fall within the circle defined by that center. Therefore, for each of the O(n^2) potential circles, we perform an O(n) operation to count the points inside. This leads to a total time complexity of O(n^2 * n), which simplifies to O(n^3).

Space Complexity

O(1) – The algorithm iterates through pairs of points and checks distances. It uses a few variables to store the current maximum count of points inside a circle and intermediate calculations like center coordinates. The space required for these variables is constant and does not depend on the number of points, N. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty points array	Return 0 immediately since no points can be inside the dartboard.
All points are the same.	The algorithm should still correctly identify that all these points are inside a circle of radius r centered on that single point.
Points are extremely far apart compared to the radius r.	The algorithm should still correctly determine the maximum number of points inside a circle, even if it is a small number.
Radius r is 0.	The only points inside the circle will be points that are exactly at the center and the algorithm should handle this edge case correctly.
Large number of points (performance)	The algorithm's complexity should be analyzed to ensure it scales reasonably with a large number of points to avoid exceeding time limits.
Floating point precision errors when calculating distances.	Use a small tolerance (epsilon) when comparing distances to the radius to account for potential floating-point inaccuracies.
Integer overflow when calculating squared distances.	Use appropriate data types (e.g., long long in C++) to avoid integer overflow when calculating squared distances.
No valid circle exists containing more than one point	The algorithm should correctly identify and return 1 if no circle contains more than one point, because we can choose one point.

Empty points array

How to Handle:

Return 0 immediately since no points can be inside the dartboard.

All points are the same.

How to Handle:

The algorithm should still correctly identify that all these points are inside a circle of radius r centered on that single point.

Points are extremely far apart compared to the radius r.

How to Handle:

The algorithm should still correctly determine the maximum number of points inside a circle, even if it is a small number.

Radius r is 0.

How to Handle:

The only points inside the circle will be points that are exactly at the center and the algorithm should handle this edge case correctly.

Large number of points (performance)

How to Handle:

The algorithm's complexity should be analyzed to ensure it scales reasonably with a large number of points to avoid exceeding time limits.

Floating point precision errors when calculating distances.

How to Handle:

Use a small tolerance (epsilon) when comparing distances to the radius to account for potential floating-point inaccuracies.

Integer overflow when calculating squared distances.

How to Handle:

Use appropriate data types (e.g., long long in C++) to avoid integer overflow when calculating squared distances.

No valid circle exists containing more than one point

How to Handle:

The algorithm should correctly identify and return 1 if no circle contains more than one point, because we can choose one point.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the data type for the coordinates of the points and the radius? Can they be floats or just integers?
What are the constraints on the number of points? Is there a maximum value for the number of points?
Is the center of the circle fixed or can I choose any point as the center?
If no points can be inside a circle of given radius, what should the function return? Should I return 0?
Are there any edge cases I should be aware of, such as points coinciding with each other or the circle's edge?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, consider every possible pair of darts as the center of a potential circle.
For each of these potential circle centers, check if all the other darts are within the specified radius of that center.
Count how many darts are inside (or on the edge) of each circle you check.
Remember the maximum number of darts you found inside any of the circles.
After checking all possible circle center positions, the largest count you remember is the answer: the maximum number of darts inside a circle.

Code Implementation

def max_darts_inside(darts, radius):
    max_darts = 0
    number_of_darts = len(darts)

    for i in range(number_of_darts):
        for j in range(i + 1, number_of_darts):
            # Consider each pair of darts as potential circle centers.

            center_x = (darts[i][0] + darts[j][0]) / 2
            center_y = (darts[i][1] + darts[j][1]) / 2

            darts_inside = 0

            for k in range(number_of_darts):
                distance = ((darts[k][0] - center_x) ** 2 + (darts[k][1] - center_y) ** 2) ** 0.5

                # Count the darts within the radius of the center
                if distance <= radius:
                    darts_inside += 1

            max_darts = max(max_darts, darts_inside)

    # Check each dart as a potential center point.
    for i in range(number_of_darts):
        center_x = darts[i][0]
        center_y = darts[i][1]
        darts_inside = 0

        for j in range(number_of_darts):
            distance = ((darts[j][0] - center_x) ** 2 + (darts[j][1] - center_y) ** 2) ** 0.5

            if distance <= radius:
                darts_inside += 1

        max_darts = max(max_darts, darts_inside)

    # Return the maximum number of darts within any circle
    return max_darts

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Consider all possible pairs of points from the given list. Each pair represents two points that could lie on the circumference of the circular dartboard.
For each pair of points, calculate the center of the possible circle passing through those two points.
Iterate through *all* the points in the given list, and for each point, check if it falls inside the circle centered at the calculated center. A point is considered inside the circle if the distance between the point and the center is less than or equal to the given radius.
Keep track of the largest number of points that fall within any of the tested circles. This maximum value is the answer.
Since each pair of points is treated as a potential base for a circle, and all other points are then checked for being inside that circle, the algorithm effectively finds the best possible circle placement for containing the most points.

Code Implementation

import math

def maximum_number_of_darts_inside(points, radius):
    number_of_points = len(points)
    if number_of_points <= 1:
        return number_of_points

    max_points_inside = 1

    for i in range(number_of_points):
        for j in range(i + 1, number_of_points):
            point1_x, point1_y = points[i]
            point2_x, point2_y = points[j]

            # Calculate the distance between the two points.
            distance_between_points = math.sqrt((point1_x - point2_x)**2 + (point1_y - point2_y)**2)

            # If the distance is greater than 2 * radius, skip.
            if distance_between_points > 2 * radius:
                continue

            # Calculate the midpoint between the two points.
            midpoint_x = (point1_x + point2_x) / 2
            midpoint_y = (point1_y + point2_y) / 2

            # Calculate the distance from midpoint to center.
            distance_to_center = math.sqrt(radius**2 - (distance_between_points / 2)**2)

            # Calculate the center 1.
            center1_x = midpoint_x + distance_to_center * (point1_y - point2_y) / distance_between_points
            center1_y = midpoint_y + distance_to_center * (point2_x - point1_x) / distance_between_points

            # Count the number of points inside the circle with center 1.
            points_inside_center1 = 0
            for k in range(number_of_points):
                point_x, point_y = points[k]
                distance_to_center1 = math.sqrt((point_x - center1_x)**2 + (point_y - center1_y)**2)
                if distance_to_center1 <= radius:
                    points_inside_center1 += 1

            max_points_inside = max(max_points_inside, points_inside_center1)

            # Calculate the center 2.
            center2_x = midpoint_x - distance_to_center * (point1_y - point2_y) / distance_between_points
            center2_y = midpoint_y - distance_to_center * (point2_x - point1_x) / distance_between_points

            # Count the number of points inside the circle with center 2.
            points_inside_center2 = 0
            for k in range(number_of_points):
                point_x, point_y = points[k]
                distance_to_center2 = math.sqrt((point_x - center2_x)**2 + (point_y - center2_y)**2)
                if distance_to_center2 <= radius:
                    points_inside_center2 += 1

            max_points_inside = max(max_points_inside, points_inside_center2)

    # Iterate through all points as possible centers
    for i in range(number_of_points):
        point_x, point_y = points[i]
        points_inside = 0
        # Check all other points if they fall within radius
        for j in range(number_of_points):
            other_point_x, other_point_y = points[j]
            distance = math.sqrt((point_x - other_point_x)**2 + (point_y - other_point_y)**2)
            if distance <= radius:
                points_inside += 1

        # Update the max points inside the circle
        max_points_inside = max(max_points_inside, points_inside)

    return max_points_inside

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty points array	Return 0 immediately since no points can be inside the dartboard.
All points are the same.	The algorithm should still correctly identify that all these points are inside a circle of radius r centered on that single point.
Points are extremely far apart compared to the radius r.	The algorithm should still correctly determine the maximum number of points inside a circle, even if it is a small number.
Radius r is 0.	The only points inside the circle will be points that are exactly at the center and the algorithm should handle this edge case correctly.
Large number of points (performance)	The algorithm's complexity should be analyzed to ensure it scales reasonably with a large number of points to avoid exceeding time limits.
Floating point precision errors when calculating distances.	Use a small tolerance (epsilon) when comparing distances to the radius to account for potential floating-point inaccuracies.
Integer overflow when calculating squared distances.	Use appropriate data types (e.g., long long in C++) to avoid integer overflow when calculating squared distances.
No valid circle exists containing more than one point	The algorithm should correctly identify and return 1 if no circle contains more than one point, because we can choose one point.

Empty points array

How to Handle:

Return 0 immediately since no points can be inside the dartboard.

All points are the same.

How to Handle:

The algorithm should still correctly identify that all these points are inside a circle of radius r centered on that single point.

Points are extremely far apart compared to the radius r.

How to Handle:

The algorithm should still correctly determine the maximum number of points inside a circle, even if it is a small number.

Radius r is 0.

How to Handle:

The only points inside the circle will be points that are exactly at the center and the algorithm should handle this edge case correctly.

Large number of points (performance)

How to Handle:

The algorithm's complexity should be analyzed to ensure it scales reasonably with a large number of points to avoid exceeding time limits.

Floating point precision errors when calculating distances.

How to Handle:

Use a small tolerance (epsilon) when comparing distances to the radius to account for potential floating-point inaccuracies.

Integer overflow when calculating squared distances.

How to Handle:

Use appropriate data types (e.g., long long in C++) to avoid integer overflow when calculating squared distances.

No valid circle exists containing more than one point

How to Handle:

The algorithm should correctly identify and return 1 if no circle contains more than one point, because we can choose one point.