1453. Maximum Number of Darts Inside of a Circular Dartboard
Explanation:
To solve this problem, we can iterate through all possible pairs of darts and consider the circle with that pair as the diameter. For each circle, we can count how many other darts lie inside or on the boundary of the circle. The circle with the maximum count of darts inside or on the boundary will be the optimal circle for placing the dartboard.
To check if a dart lies inside a circle, we can calculate the distance between the center of the circle and the dart. If this distance is less than or equal to the radius of the circle, the dart lies inside or on the boundary of the circle.
Time Complexity:
The time complexity of this approach is O(n^3), where n is the number of darts.
Space Complexity:
The space complexity of this approach is O(1) as we are not using any extra space apart from a few variables.
:
class Solution {
public int numPoints(int[][] darts, int r) {
int n = darts.length;
int maxDarts = 1;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
double[] center = {(darts[i][0] + darts[j][0]) / 2.0, (darts[i][1] + darts[j][1]) / 2.0};
double distance = Math.sqrt(Math.pow(darts[i][0] - center[0], 2) + Math.pow(darts[i][1] - center[1], 2));
if (distance > r) continue;
int count = 2;
for (int k = 0; k < n; k++) {
if (k != i && k != j) {
double dist = Math.sqrt(Math.pow(darts[k][0] - center[0], 2) + Math.pow(darts[k][1] - center[1], 2));
if (dist <= r) {
count++;
}
}
}
maxDarts = Math.max(maxDarts, count);
}
}
return maxDarts;
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.