Scale Engineer

Queries on Number of Points Inside a Circle

Med
#1671Time: `O(N * M)`, where `N` is the number of points and `M` is the number of queries. We have nested loops iterating through all queries and all points.Space: `O(M)` to store the result array. If the output array is not considered part of the space complexity, it is `O(1)`.
Patterns
MathGeometry
Data structures
Array

Prompt

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.

 

Constraints:

  • 1 <= points.length <= 500
  • points[i].length == 2
  • 0 <= x​​​​​​i, y​​​​​​i <= 500
  • 1 <= queries.length <= 500
  • queries[j].length == 3
  • 0 <= xj, yj <= 500
  • 1 <= rj <= 500
  • All coordinates are integers.

 

Follow up: Could you find the answer for each query in better complexity than O(n)?

Approaches

3 approaches with complexity analysis and trade-offs.

The most straightforward solution is to check every point for every query. For each circle defined in the queries array, we iterate through the entire points array. For each point, we calculate its distance from the circle's center and check if it's less than or equal to the radius.

Algorithm

  • Initialize an integer array answer with the same size as queries.
  • For each query j in queries:
    • Extract the circle's center (cx, cy) and radius r.
    • Initialize a counter current_count to 0.
    • For each point i in points:
      • Extract the point's coordinates (px, py).
      • Calculate the squared distance: dist_sq = (px - cx)² + (py - cy)².
      • If dist_sq is less than or equal to r², increment current_count.
    • Store current_count in answer[j].
  • Return answer.

Walkthrough

To implement this, we loop through each query. Inside this loop, we have another loop that goes through all the points. The core of the logic is the distance check. A point (px, py) is inside or on the border of a circle with center (cx, cy) and radius r if the Euclidean distance between them is at most r. This is expressed by the formula sqrt((px - cx)² + (py - cy)²) <= r. To avoid floating-point arithmetic and the computationally expensive square root operation, we can compare the squared distances instead: (px - cx)² + (py - cy)² <= r². This is more efficient and avoids potential precision issues. We maintain a count for each query and store the final counts in the result array.

class Solution {    public int[] countPoints(int[][] points, int[][] queries) {        int m = queries.length;        int[] answer = new int[m];         for (int i = 0; i < m; i++) {            int cx = queries[i][0];            int cy = queries[i][1];            int r = queries[i][2];            int rSquared = r * r;            int count = 0;             for (int[] point : points) {                int px = point[0];                int py = point[1];                                int dx = px - cx;                int dy = py - cy;                 if (dx * dx + dy * dy <= rSquared) {                    count++;                }            }            answer[i] = count;        }                return answer;    }}

Complexity

Time

`O(N * M)`, where `N` is the number of points and `M` is the number of queries. We have nested loops iterating through all queries and all points.

Space

`O(M)` to store the result array. If the output array is not considered part of the space complexity, it is `O(1)`.

Trade-offs

Pros

  • Simple to understand and implement.

  • Requires no complex data structures.

  • Sufficiently fast for the given problem constraints.

Cons

  • Inefficient for very large datasets.

  • Time complexity scales linearly with both the number of points and queries.

Solutions

class Solution { public int [] countPoints ( int [][] points , int [][] queries ) { int m = queries . length ; int [] ans = new int [ m ]; for ( int k = 0 ; k < m ; ++ k ) { int x = queries [ k ][ 0 ], y = queries [ k ][ 1 ], r = queries [ k ][ 2 ]; for ( var p : points ) { int i = p [ 0 ], j = p [ 1 ]; int dx = i - x , dy = j - y ; if ( dx * dx + dy * dy <= r * r ) { ++ ans [ k ]; } } } return ans ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem