1453. Maximum Number of Darts Inside of a Circular Dartboard LeetCode Solution
In this guide, you will get 1453. Maximum Number of Darts Inside of a Circular Dartboard LeetCode Solution with the best time and space complexity. The solution to Maximum Number of Darts Inside of a Circular Dartboard problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Maximum Number of Darts Inside of a Circular Dartboard solution in C++
- Maximum Number of Darts Inside of a Circular Dartboard solution in Java
- Maximum Number of Darts Inside of a Circular Dartboard solution in Python
- Additional Resources
Problem Statement of Maximum Number of Darts Inside of a Circular Dartboard
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 ith 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
-104 <= xi, yi <= 104
All the darts are unique
1 <= r <= 5000
Complexity Analysis
- Time Complexity: O(n^3)
- Space Complexity: O(n)
1453. Maximum Number of Darts Inside of a Circular Dartboard LeetCode Solution in C++
struct Point {
double x;
double y;
Point(double x, double y) : x(x), y(y) {}
};
class Solution {
public:
int numPoints(vector<vector<int>>& darts, int r) {
int ans = 1;
vector<Point> points = convertToPoints(darts);
for (int i = 0; i < points.size(); ++i)
for (int j = i + 1; j < points.size(); ++j)
for (const Point& c : getCircles(points[i], points[j], r)) {
int count = 0;
for (const Point& point : points)
if (dist(c, point) - r <= kErr)
++count;
ans = max(ans, count);
}
return ans;
}
private:
static constexpr double kErr = 1e-6;
vector<Point> convertToPoints(const vector<vector<int>>& darts) {
vector<Point> points;
for (const vector<int>& dart : darts)
points.emplace_back(dart[0], dart[1]);
return points;
}
vector<Point> getCircles(const Point& p, const Point& q, int r) {
if (dist(p, q) - 2.0 * r > kErr)
return {};
const Point m{(p.x + q.x) / 2, (p.y + q.y) / 2};
const double distCM = sqrt(pow(r, 2) - pow(dist(p, q) / 2, 2));
const double alpha = atan2(p.y - q.y, q.x - p.x);
return {Point{m.x - distCM * sin(alpha), m.y - distCM * cos(alpha)},
Point{m.x + distCM * sin(alpha), m.y + distCM * cos(alpha)}};
}
double dist(const Point& p, const Point& q) {
return sqrt(pow(p.x - q.x, 2) + pow(p.y - q.y, 2));
}
};
/* code provided by PROGIEZ */1453. Maximum Number of Darts Inside of a Circular Dartboard LeetCode Solution in Java
class Point {
public double x = 0;
public double y = 0;
public Point(double x, double y) {
this.x = x;
this.y = y;
}
}
class Solution {
public int numPoints(int[][] darts, int r) {
int ans = 1;
List<Point> points = convertToPoints(darts);
for (int i = 0; i < points.size(); ++i)
for (int j = i + 1; j < points.size(); ++j)
for (Point c : getCircles(points.get(i), points.get(j), r)) {
int count = 0;
for (Point point : points)
if (dist(c, point) - r <= kErr)
++count;
ans = Math.max(ans, count);
}
return ans;
}
private static final double kErr = 1e-6;
private List<Point> convertToPoints(int[][] darts) {
List<Point> points = new ArrayList<>();
for (int[] dart : darts)
points.add(new Point(dart[0], dart[1]));
return points;
}
private Point[] getCircles(Point p, Point q, int r) {
if (dist(p, q) - 2.0 * r > kErr)
return new Point[] {};
Point m = new Point((p.x + q.x) / 2, (p.y + q.y) / 2);
final double distCM = Math.sqrt(Math.pow(r, 2) - Math.pow(dist(p, q) / 2, 2));
final double alpha = Math.atan2(p.y - q.y, q.x - p.x);
return new Point[] {new Point(m.x - distCM * Math.sin(alpha), m.y - distCM * Math.cos(alpha)),
new Point(m.x + distCM * Math.sin(alpha), m.y + distCM * Math.cos(alpha))};
}
private double dist(Point p, Point q) {
return Math.sqrt(Math.pow(p.x - q.x, 2) + Math.pow(p.y - q.y, 2));
}
}
// code provided by PROGIEZ1453. Maximum Number of Darts Inside of a Circular Dartboard LeetCode Solution in Python
class Point:
def __init__(self, x: float, y: float):
self.x = x
self.y = y
class Solution:
def numPoints(self, darts: list[list[int]], r: int) -> int:
kErr = 1e-6
ans = 1
points = [Point(x, y) for x, y in darts]
def dist(p: Point, q: Point) -> float:
return ((p.x - q.x)**2 + (p.y - q.y)**2)**0.5
def getCircles(p: Point, q: Point) -> list[Point]:
if dist(p, q) - 2.0 * r > kErr:
return []
m = Point((p.x + q.x) / 2, (p.y + q.y) / 2)
distCM = (r**2 - (dist(p, q) / 2)**2)**0.5
alpha = math.atan2(p.y - q.y, q.x - p.x)
return [Point(m.x - distCM * math.sin(alpha), m.y - distCM * math.cos(alpha)),
Point(m.x + distCM * math.sin(alpha), m.y + distCM * math.cos(alpha))]
for i in range(len(points)):
for j in range(i + 1, len(points)):
for c in getCircles(points[i], points[j]):
count = 0
for point in points:
if dist(c, point) - r <= kErr:
count += 1
ans = max(ans, count)
return ans
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.