1828. Queries on Number of Points Inside a Circle LeetCode Solution
In this guide, you will get 1828. Queries on Number of Points Inside a Circle LeetCode Solution with the best time and space complexity. The solution to Queries on Number of Points Inside a Circle 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.
Problem Statement of Queries on Number of Points Inside a Circle
You are given an array points where points[i] = [xi, yi] is the coordinates of the ith point on a 2D plane. Multiple points can have the same coordinates.
You are also given an array queries where queries[j] = [xj, yj, rj] describes a circle centered at (xj, yj) with a radius of rj.
For each query queries[j], compute the number of points inside the jth circle. Points on the border of the circle are considered inside.
Return an array answer, where answer[j] is the answer to the jth query.
Example 1:
Input: points = [[1,3],[3,3],[5,3],[2,2]], queries = [[2,3,1],[4,3,1],[1,1,2]]
Output: [3,2,2]
Explanation: The points and circles are shown above.
queries[0] is the green circle, queries[1] is the red circle, and queries[2] is the blue circle.
Example 2:
Input: points = [[1,1],[2,2],[3,3],[4,4],[5,5]], queries = [[1,2,2],[2,2,2],[4,3,2],[4,3,3]]
Output: [2,3,2,4]
Explanation: The points and circles are shown above.
queries[0] is green, queries[1] is red, queries[2] is blue, and queries[3] is purple.
Follow up: Could you find the answer for each query in better complexity than O(n)?
Complexity Analysis
Time Complexity: O(q|\texttt{points}|)
Space Complexity: O(q)
1828. Queries on Number of Points Inside a Circle LeetCode Solution in C++
class Solution {
public:
vector<int> countPoints(vector<vector<int>>& points,
vector<vector<int>>& queries) {
vector<int> ans;
for (const vector<int>& query : queries) {
const int xj = query[0];
const int yj = query[1];
const int rj = query[2];
int count = 0;
for (const vector<int>& point : points) {
const int xi = point[0];
const int yi = point[1];
if (squared(xi - xj) + squared(yi - yj) <= squared(rj))
++count;
}
ans.push_back(count);
}
return ans;
}
private:
int squared(int x) {
return x * x;
}
}; /* code provided by PROGIEZ */
1828. Queries on Number of Points Inside a Circle LeetCode Solution in Java
class Solution {
public int[] countPoints(int[][] points, int[][] queries) {
int[] ans = new int[queries.length];
for (int i = 0; i < queries.length; ++i) {
final int xj = queries[i][0];
final int yj = queries[i][1];
final int rj = queries[i][2];
int count = 0;
for (int[] point : points) {
final int xi = point[0];
final int yi = point[1];
if (squared(xi - xj) + squared(yi - yj) <= squared(rj))
++count;
}
ans[i] = count;
}
return ans;
}
private int squared(int x) {
return x * x;
}
} // code provided by PROGIEZ
1828. Queries on Number of Points Inside a Circle LeetCode Solution in Python
class Solution:
def countPoints(
self,
points: list[list[int]],
queries: list[list[int]],
) -> list[int]:
ans = []
for xj, yj, rj in queries:
count = 0
for xi, yi in points:
if (xi - xj)**2 + (yi - yj)**2 <= rj**2:
count += 1
ans.append(count)
return ans # code by PROGIEZ
