Leetcode 1828: Queries on Number of Points Inside a Circle
You are given an array of points, each represented by its coordinates [xi, yi] on a 2D plane. You are also given an array of queries, where each query describes a circle defined by its center at (xj, yj) and its radius rj. For each query, your task is to compute how many points lie inside or on the border of the circle.
Problem
Approach
Steps
Complexity
Input: You are given two arrays. The first array, points, consists of pairs of integers where each pair represents the coordinates of a point. The second array, queries, consists of triplets where each triplet represents the center coordinates (xj, yj) and the radius rj of a circle.
Example: For example, points = [[1,3], [3,3], [5,3], [2,2]] represents 4 points, and queries = [[2,3,1], [4,3,1], [1,1,2]] represents 3 circles.
Constraints:
• 1 <= points.length <= 500
• points[i].length == 2
• 0 <= xi, yi <= 500
• 1 <= queries.length <= 500
• queries[j].length == 3
• 0 <= xj, yj <= 500
• 1 <= rj <= 500
Output: Return an array of integers where each element is the number of points inside or on the border of the corresponding circle defined in the queries array.
Example: For points = [[1,3],[3,3],[5,3],[2,2]] and queries = [[2,3,1],[4,3,1],[1,1,2]], the output will be [3, 2, 2], as there are 3 points inside or on the first circle, 2 points inside or on the second, and 2 points inside or on the third circle.
Constraints:
• Each answer in the result should be an integer.
Goal: For each query, calculate how many points are inside the circle. The circle includes the points on its border as well.
Steps:
• 1. For each query, loop through each point and calculate the squared distance from the point to the center of the circle.
• 2. If the squared distance is less than or equal to the squared radius, increment the count for that query.
• 3. After processing all points for a query, store the count as the result for that query.
Goal: Make sure to handle the queries efficiently within the given constraints of the input sizes.
Steps:
• Each query's circle must be evaluated for all points in the input array.
• The input size can go up to 500 points and 500 queries.
Assumptions:
• Each point is represented as a pair of integers (xi, yi), and each query as a triplet (xj, yj, rj).
• A point is considered inside or on the border of the circle if its distance from the center is less than or equal to the radius.
• Input: Input: points = [[1,3], [3,3], [5,3], [2,2]], queries = [[2,3,1], [4,3,1], [1,1,2]]
• Explanation: The first circle is centered at (2,3) with radius 1, which includes the points [1,3], [2,2], and [3,3], so the answer is 3. The second circle at (4,3) with radius 1 includes points [3,3] and [5,3], so the answer is 2. The third circle at (1,1) with radius 2 includes points [1,3] and [2,2], so the answer is 2.
• Input: 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]]
• Explanation: The first circle includes the points [1,1] and [2,2], so the answer is 2. The second circle includes [1,1], [2,2], and [3,3], so the answer is 3. The third circle includes [4,4] and [5,5], so the answer is 2. The fourth circle includes all points, so the answer is 4.
Approach: We can solve this problem by checking each point for each query, calculating the distance to the center of the circle, and counting how many points fall inside the circle.
Observations:
• A point is inside or on the border of the circle if the squared distance from the point to the center is less than or equal to the squared radius of the circle.
• The brute force solution checks each point against every query, which results in O(n * q) time complexity, where n is the number of points and q is the number of queries.
Steps:
• 1. For each query, initialize a counter to track the number of points inside the circle.
• 2. For each point, calculate the squared distance from the center of the circle to the point.
• 3. If the squared distance is less than or equal to the square of the radius, increment the counter.
• 4. After processing all points for a query, add the count to the result list.
Empty Inputs:
• If no points are provided, the result should be an array of zeros.
Large Inputs:
• If the number of points and queries is large (up to 500 each), ensure the algorithm can handle the maximum input size.
Special Values:
• If all points are identical, consider that all queries should include these points based on their radius.
Constraints:
• Ensure the solution handles large values efficiently within the given time limits.
class Solution {
typedef vector<vector<int>> mo;
public:
vector<int> countPoints(mo& pts, mo& qrs) {
vector<int> res;
for(auto &q: qrs) {
int cnt = 0, rr = q[2] * q[2];
for(auto &p: pts)
cnt += (q[0] - p[0]) * (q[0] - p[0]) + (q[1] - p[1]) * (q[1] - p[1]) <= rr;
res.push_back(cnt);
}
return res;
}
1 : Class Definition
class Solution {
Defines the `Solution` class, which contains the method `countPoints` to solve the problem.
2 : Typedef Declaration
typedef vector<vector<int>> mo;
This line defines a shorthand type `mo` for a 2D vector of integers. It is used to represent both the list of points and queries in the method.
3 : Public Access Modifier
public:
Marks the start of the public section of the class, where methods are accessible outside the class.
4 : Function Definition
vector<int> countPoints(mo& pts, mo& qrs) {
Defines the function `countPoints`, which takes two 2D vectors: `pts` (points) and `qrs` (queries). It returns a vector of integers representing the count of points within the radius for each query.
5 : Result Initialization
vector<int> res;
Initializes an empty vector `res` to store the result: the count of points inside each query's circle.
6 : Loop Through Queries
for(auto &q: qrs) {
Begins a loop to iterate through each query in `qrs`. Each query represents a circle defined by its center coordinates and radius.
7 : Query Initialization
int cnt = 0, rr = q[2] * q[2];
Initializes `cnt` to 0 to count the points within the circle and calculates `rr`, the square of the radius (radius squared) for distance comparison.
8 : Loop Through Points
for(auto &p: pts)
Starts a nested loop to iterate over each point in the `pts` vector.
9 : Distance Check
cnt += (q[0] - p[0]) * (q[0] - p[0]) + (q[1] - p[1]) * (q[1] - p[1]) <= rr;
For each point `p`, this line calculates the squared distance between the point and the center of the query circle. If the squared distance is less than or equal to `rr`, it increments the count `cnt`.
10 : Store Result
res.push_back(cnt);
After checking all points for the current query, the count of points within the circle (`cnt`) is added to the result vector `res`.
11 : Return Result
return res;
Returns the result vector `res` containing the counts of points within each query circle.
Best Case: O(n * q) when the points are sparse and the circles have small radii.
Average Case: O(n * q), where n is the number of points and q is the number of queries.
Worst Case: O(n * q), which occurs when every point must be checked for every query.
Description: The time complexity is O(n * q) because we are iterating over each query and checking each point.
Best Case: O(n + q), which is required to store the points and queries.
Worst Case: O(n + q), which is required to store the points and the queries.
Description: The space complexity is O(n + q) because we store both the points and queries arrays.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus