Queries On Number Of Points Inside A Circle - Leetcode Solution

Problem Description:

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.

Solution:

The problem states that we are given an array of 2D points. It also gives us an array of circles with centers and radii.

To solve this problem, we need to iterate through each query and check whether a point lies inside the circle or not. We can use the Euclidean distance formula to check whether a point lies inside the circle or not.

Euclidean distance formula:

d = sqrt((x2-x1)^2 + (y2-y1)^2)

Here, (x1, y1) are the coordinates of the center of the circle and (x2, y2) are the coordinates of the point. If the distance d is less than or equal to the radius, then the point lies inside the circle.

We can use this formula to iterate through all the points and count the number of points lying inside the circle. We can do this for all the circles in the query array and store the counts in an answer array.

Algorithm:

1. Initialize an answer array with zeros of length queries.length.
2. Iterate through all the circles (xj, yj, rj) in the queries array.
3. For each circle, iterate through all the points (xi, yi) in the points array and check if the point lies inside the circle.
4. If a point lies inside the circle, increment the count.
5. After iterating through all the points, store the count in the answer array at the index corresponding to the circle.
6. Return the answer array.

Code:

function countPoints(points, queries) { const answer = Array(queries.length).fill(0); for (let i = 0; i < queries.length; i++) { const [xj, yj, rj] = queries[i]; for (let j = 0; j < points.length; j++) { const [xi, yi] = points[j]; const d = Math.sqrt((xi - xj) ** 2 + (yi - yj) ** 2); if (d <= rj) { answer[i]++; } } } return answer; }

Time Complexity: O(n * m), where n is the length of the queries array and m is the length of the points array.

Space Complexity: O(n), where n is the length of the queries array.

This solution has a time complexity of O(n * m) which is not very efficient. We can optimize this solution by using a more efficient approach. We can use an algorithm that searches through points within the range of the circle instead of iterating through all the points.

One of the most popular algorithms to search through points within a range is the k-d tree algorithm. The k-d tree algorithm structures the points in a tree-like data structure, which makes searching through points very efficient.

However, since the problem input size is relatively small, the above straightforward approach works efficiently and is quite easy to implement and understand.

1