Leetcode 1828. Queries on Number of Points Inside a Circle Solution
Problem Explanation
We are given a list of 2D points with their (x, y) coordinates, and a list of circles described by their center coordinates (x_j, y_j) and their radius r_j. Each circle is represented as a query. The task is to find out how many points from the given list of points lie inside each circle (query). Points that lie on the border of a circle are also considered inside the circle. We need to return the answer as an array with the count of points inside each query circle.
Walk through an example
Let's walk through an example to better understand the problem:
1points = [[1,3],[3,3],[5,3],[2,2]] 2queries = [[2,3,1],[4,3,1],[1,1,2]]
For each query circle, we need to count how many points lie inside it.
- For the first query circle with center (2, 3) and radius 1, there are 3 points inside it: (1, 3), (2, 2), (3, 3)
- For the second query circle with center (4, 3) and radius 1, there are 2 points inside it: (3, 3), (5, 3)
- For the third query circle with center (1, 1) and radius 2, there are 2 points inside it: (1, 3), (2, 2)
So, the final answer would be [3, 2, 2].
Solution Approach
The basic approach to this problem is to loop through all the points of each circle in the queries list and check if the point lies inside the circle or not.
In order to check whether a point (x_i, y_i) lies inside a circle with center (x_j, y_j) and radius r_j, we can calculate the Euclidean distance between the point and the circle's center and check if it is less than or equal to the radius. The Euclidean distance can be calculated using the following formula:
1euclidean_distance = sqrt((x_i - x_j)^2 + (y_i - y_j)^2)
However, since we are only interested in the square of the distance, we can avoid using the square root operation, which makes the comparison faster:
1squared_distance = (x_i - x_j)^2 + (y_i - y_j)^2
We can now compare squared_distance with r_j^2 for each point and circle center.
Solution in Python
1from typing import List
2
3class Solution:
4 def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:
5 def squared_distance(x1, y1, x2, y2) -> int:
6 return (x1 - x2) ** 2 + (y1 - y2) ** 2
7
8 ans = []
9 for q in queries:
10 xj, yj, rj = q
11 count = 0
12 for p in points:
13 xi, yi = p
14 if squared_distance(xi, yi, xj, yj) <= rj ** 2:
15 count += 1
16 ans.append(count)
17
18 return ans
Solution in Java
1import java.util.ArrayList;
2import java.util.List;
3
4class Solution {
5 private int squaredDistance(int x1, int y1, int x2, int y2) {
6 return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
7 }
8
9 public List<Integer> countPoints(int[][] points, int[][] queries) {
10 List<Integer> ans = new ArrayList<>();
11 for (int[] query : queries) {
12 int xj = query[0], yj = query[1], rj = query[2];
13 int count = 0;
14 for (int[] point : points) {
15 int xi = point[0], yi = point[1];
16 if (squaredDistance(xi, yi, xj, yj) <= rj * rj) {
17 count++;
18 }
19 }
20 ans.add(count);
21 }
22 return ans;
23 }
24}
Solution in JavaScript
1class Solution {
2 static squaredDistance(x1, y1, x2, y2) {
3 return (x1 - x2) ** 2 + (y1 - y2) ** 2;
4 }
5
6 static countPoints(points, queries) {
7 const ans = [];
8 for (const query of queries) {
9 const xj = query[0], yj = query[1], rj = query[2];
10 let count = 0;
11 for (const point of points) {
12 const xi = point[0], yi = point[1];
13 if (this.squaredDistance(xi, yi, xj, yj) <= rj ** 2) {
14 count++;
15 }
16 }
17 ans.push(count);
18 }
19 return ans;
20 }
21}
Solution in C++
1#include <vector>
2
3class Solution {
4public:
5 int squaredDistance(int x1, int y1, int x2, int y2) {
6 return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
7 }
8
9 std::vector<int> countPoints(std::vector<std::vector<int>>& points, std::vector<std::vector<int>>& queries) {
10 std::vector<int> ans;
11 for (const std::vector<int>& query : queries) {
12 int xj = query[0], yj = query[1], rj = query[2];
13 int count = 0;
14 for (const std::vector<int>& point : points) {
15 int xi = point[0], yi = point[1];
16 if (squaredDistance(xi, yi, xj, yj) <= rj * rj) {
17 count++;
18 }
19 }
20 ans.push_back(count);
21 }
22 return ans;
23 }
24};
Solution in C#
1using System.Collections.Generic;
2
3public class Solution {
4 private int SquaredDistance(int x1, int y1, int x2, int y2) {
5 return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
6 }
7
8 public IList<int> CountPoints(int[][] points, int[][] queries) {
9 List<int> ans = new List<int>();
10 foreach (int[] query in queries) {
11 int xj = query[0], yj = query[1], rj = query[2];
12 int count = 0;
13 foreach (int[] point in points) {
14 int xi = point[0], yi = point[1];
15 if (SquaredDistance(xi, yi, xj, yj) <= rj * rj) {
16 count++;
17 }
18 }
19 ans.Add(count);
20 }
21 return ans;
22 }
23}
The solutions provided in all the languages have a complexity of O(n^2) where n is the length of the points and queries list. A more optimized solution would involve using a more advanced data structure like k-d tree or spatial hashing to reduce the lookup complexity.However, considering the constraints of the problem statement, the given solutions should pass the required test cases efficiently.
In summary, the problem involves checking whether a given point lies within a circle's boundary or not. To find if a point lies inside a circle, we calculate the squared Euclidean distance between the point and the circle's center and compare this value to the square of the circle's radius. We then count the number of points within each circle described by the queries list, and return the result as an array. We provided implementations for this approach in Python, Java, JavaScript, C++, and C# languages.