Queries on Number of Points Inside a Circle
MedPrompt
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 <= 500points[i].length == 20 <= xi, yi <= 5001 <= queries.length <= 500queries[j].length == 30 <= xj, yj <= 5001 <= 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
answerwith the same size asqueries. - For each query
jinqueries:- Extract the circle's center
(cx, cy)and radiusr. - Initialize a counter
current_countto 0. - For each point
iinpoints:- Extract the point's coordinates
(px, py). - Calculate the squared distance:
dist_sq = (px - cx)² + (py - cy)². - If
dist_sqis less than or equal tor², incrementcurrent_count.
- Extract the point's coordinates
- Store
current_countinanswer[j].
- Extract the circle's center
- 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.
A more optimized approach involves using a spatial hashing technique. We can divide the 2D plane into a grid of cells (or "buckets") and pre-process the points by placing them into the appropriate bucket based on their coordinates. When a query for a circle is made, we only need to check the points in the buckets that the circle intersects, significantly reducing the number of points to check compared to the brute-force method.
Algorithm
- Define a
cellSizeand create a 2D grid of lists (buckets). - For each point
pinpoints, calculate its bucket indices(bx, by)and addptobuckets[bx][by]. - Initialize an
answerarray. - For each query circle
(cx, cy, r):- Calculate the range of bucket indices
(minBX, maxBX)and(minBY, maxBY)that the circle's bounding box intersects. - Initialize
count = 0. - Iterate through each bucket
(bx, by)in the calculated range.- For each point
pinbuckets[bx][by]:- Check if
pis inside the circle. - If it is, increment
count.
- Check if
- For each point
- Store
countin theanswerarray.
- Calculate the range of bucket indices
- Return
answer.
Walkthrough
First, we choose a suitable cell size for our grid. This choice affects the trade-off between the number of buckets to check and the number of points per bucket. After setting up a 2D array of lists to represent the grid, we iterate through all points, placing each into its corresponding bucket. For each query, we identify the rectangular area of buckets that the circle's bounding box covers. Then, we iterate only through the points within this smaller set of buckets, performing the distance check for each. This prunes the search space effectively, especially when points are somewhat uniformly distributed.
import java.util.ArrayList;import java.util.List; class Solution { public int[] countPoints(int[][] points, int[][] queries) { // The maximum coordinate value is 500. int maxCoord = 501; // Choose a cell size for the grid. This is a tunable parameter. int cellSize = 25; int numCells = (maxCoord + cellSize - 1) / cellSize; List<int[]>[][] buckets = new ArrayList[numCells][numCells]; for (int i = 0; i < numCells; i++) { for (int j = 0; j < numCells; j++) { buckets[i][j] = new ArrayList<>(); } } // Place each point into its corresponding bucket. for (int[] p : points) { int bx = p[0] / cellSize; int by = p[1] / cellSize; buckets[bx][by].add(p); } int[] ans = new int[queries.length]; for (int i = 0; i < queries.length; i++) { int cx = queries[i][0]; int cy = queries[i][1]; int r = queries[i][2]; long rSquared = (long)r * r; int count = 0; // Determine the range of buckets to check based on the circle's bounding box. int minBX = Math.max(0, (cx - r) / cellSize); int maxBX = Math.min(numCells - 1, (cx + r) / cellSize); int minBY = Math.max(0, (cy - r) / cellSize); int maxBY = Math.min(numCells - 1, (cy + r) / cellSize); // Iterate through the relevant buckets and check points. for (int bx = minBX; bx <= maxBX; bx++) { for (int by = minBY; by <= maxBY; by++) { for (int[] p : buckets[bx][by]) { long dx = p[0] - cx; long dy = p[1] - cy; if (dx * dx + dy * dy <= rSquared) { count++; } } } } ans[i] = count; } return ans; }}Complexity
Time
The average time complexity is better than brute force. Preprocessing takes `O(N)`. A query takes `O(k + m)` where `k` is the number of points in the checked buckets and `m` is the number of checked buckets. In the worst case (all points in one bucket), it degrades to `O(N * M)`.
Space
`O(N + G)`, where `N` is for storing the points in buckets and `G` is the number of cells in the grid (`G = (max_coord / cell_size)^2`).
Trade-offs
Pros
Faster on average than brute force for many data distributions.
Relatively simple to implement compared to more complex spatial trees.
Offers a good trade-off between performance and implementation effort.
Cons
Performance depends on the choice of
cellSizeand the data distribution.Worst-case time complexity is the same as brute force.
Uses more memory than the brute-force approach.
To achieve a solution with better asymptotic complexity, as suggested by the follow-up, we can use a sophisticated spatial data structure like a K-D tree. A K-D tree partitions the 2D space by recursively splitting the set of points along alternating axes. This allows for efficient range searching, which is exactly what a circular query is.
Algorithm
- Build Phase:
- Define a
Nodestructure for the tree. - Create a recursive
buildfunction that takes a list of points and a depth. - It determines the splitting axis (x or y based on depth).
- It finds the median point along that axis, makes it the current node.
- It recursively calls
buildfor points on either side of the median to form the left and right subtrees.
- Define a
- Query Phase:
- For each query circle, call a recursive
searchfunction starting from the root. - In the
searchfunction at a givennode:- If the node is null, return 0.
- Check if the point at the current node is inside the circle; if so, add 1 to the count.
- Determine which child subtree is "nearer" to the circle's center and recurse into it.
- Check if the circle intersects the splitting plane. If it does, it's possible points in the "far" subtree are also in the circle, so recurse into the far subtree as well.
- Sum the counts from the recursive calls and the current node.
- For each query circle, call a recursive
Walkthrough
The process has two main phases. First, we build the K-D tree from the input points, which takes O(N log N) time. This involves recursively finding the median point along an axis and splitting the remaining points into two subtrees. Second, for each query, we traverse the K-D tree to find points inside the circle. At each node, we check if the node's point is inside the circle. Then, we determine if we need to explore the child subtrees. We can prune a subtree if its entire rectangular region lies outside the query circle, which is the source of the efficiency gain. This avoids checking a large number of points that are far away from the query circle.
import java.util.Arrays;import java.util.Comparator; class Solution { private static class Node { int[] point; Node left, right; Node(int[] point) { this.point = point; } } public int[] countPoints(int[][] points, int[][] queries) { // To avoid modifying the original points array during sorting for tree build int[][] pointsCopy = Arrays.copyOf(points, points.length); Node root = buildKdTree(pointsCopy, 0, points.length - 1, 0); int[] result = new int[queries.length]; for (int i = 0; i < queries.length; i++) { result[i] = searchKdTree(root, queries[i], 0); } return result; } private Node buildKdTree(int[][] points, int start, int end, int depth) { if (start > end) { return null; } int axis = depth % 2; // Sorting at each step leads to O(N log^2 N) build time. // A linear-time median-finding algorithm would optimize this to O(N log N). Arrays.sort(points, start, end + 1, Comparator.comparingInt(p -> p[axis])); int mid = start + (end - start) / 2; Node node = new Node(points[mid]); node.left = buildKdTree(points, start, mid - 1, depth + 1); node.right = buildKdTree(points, mid + 1, end, depth + 1); return node; } private int searchKdTree(Node node, int[] query, int depth) { if (node == null) { return 0; } int cx = query[0], cy = query[1], r = query[2]; long rSquared = (long)r * r; int count = 0; // 1. Check if the current node's point is in the circle long distSq = (long)(node.point[0] - cx) * (node.point[0] - cx) + (long)(node.point[1] - cy) * (node.point[1] - cy); if (distSq <= rSquared) { count++; } int axis = depth % 2; // Distance from circle center to the splitting plane long axisDist = (axis == 0) ? (long)cx - node.point[0] : (long)cy - node.point[1]; // 2. Traverse subtrees // First, traverse the subtree on the same side as the circle's center Node nearNode = (axisDist < 0) ? node.left : node.right; Node farNode = (axisDist < 0) ? node.right : node.left; count += searchKdTree(nearNode, query, depth + 1); // 3. Traverse the other subtree only if the circle could cross the splitting plane if (axisDist * axisDist <= rSquared) { count += searchKdTree(farNode, query, depth + 1); } return count; }}Complexity
Time
`O(N log N + M * sqrt(N))` on average. Building the tree is `O(N log N)`. A single query in a balanced 2D K-D tree takes `O(sqrt(N))` on average. In the worst case, complexity can degrade towards `O(N*M)`.
Space
`O(N)` to store the K-D tree structure.
Trade-offs
Pros
Asymptotically the most efficient approach.
Significantly outperforms brute force on large and uniformly distributed datasets.
Directly addresses the follow-up question for a better-than-linear per-query solution.
Cons
Much more complex to implement correctly and efficiently.
Implementation overhead might make it slower than simpler approaches for small N and M.
Performance can degrade significantly for non-uniform or pathological data distributions.
Solutions
Solution
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 ; } }class Solution { public: vector < int > countPoints ( vector < vector < int >>& points , vector < vector < int >>& queries ) { vector < int > ans ; for ( auto & q : queries ) { int x = q [ 0 ], y = q [ 1 ], r = q [ 2 ]; int cnt = 0 ; for ( auto & p : points ) { int i = p [ 0 ], j = p [ 1 ]; int dx = i - x , dy = j - y ; cnt += dx * dx + dy * dy <= r * r ; } ans . emplace_back ( cnt ); } return ans ; } };class Solution : def countPoints ( self , points : List [ List [ int ]], queries : List [ List [ int ]] ) -> List [ int ]: ans = [] for x , y , r in queries : cnt = 0 for i , j in points : dx , dy = i - x , j - y cnt += dx * dx + dy * dy <= r * r ans . append ( cnt ) return ansVideo 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.