# Queries on Number of Points Inside a Circle
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/queries-on-number-of-points-inside-a-circle)
Canonical: https://scaleengineer.com/dsa/problems/queries-on-number-of-points-inside-a-circle
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Geometry](https://scaleengineer.com/dsa/patterns/geometry)
**Data structures:** Array
---
## Problem
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:**

![](https://assets.glich.co/dsa/queries-on-number-of-points-inside-a-circle/image0.png) 

**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:**

![](https://assets.glich.co/dsa/queries-on-number-of-points-inside-a-circle/image1.png) 

**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
## Brute Force Iteration
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.
**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)`.
**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.
### Explanation
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.
```java
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;
    }
}
```
### 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`.

## Grid-Based Bucketing (Spatial Hashing)
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.
**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`).
**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 `cellSize` and the data distribution.; Worst-case time complexity is the same as brute force.; Uses more memory than the brute-force approach.
### Explanation
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.
```java
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;
    }
}
```
### Algorithm
- Define a `cellSize` and create a 2D grid of lists (buckets).
- For each point `p` in `points`, calculate its bucket indices `(bx, by)` and add `p` to `buckets[bx][by]`.
- Initialize an `answer` array.
- 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 `p` in `buckets[bx][by]`:
      - Check if `p` is inside the circle.
      - If it is, increment `count`.
  - Store `count` in the `answer` array.
- Return `answer`.

## Spatial Indexing with a K-D Tree
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.
**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.
**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.
### Explanation
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.
```java
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;
    }
}
```
### Algorithm
- **Build Phase:**
  - Define a `Node` structure for the tree.
  - Create a recursive `build` function 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 `build` for points on either side of the median to form the left and right subtrees.
- **Query Phase:**
  - For each query circle, call a recursive `search` function starting from the root.
  - In the `search` function at a given `node`:
    - 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.

# Solutions
### Java

```java
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 ; } }
```

### CPP

```cpp
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 ; } };
```

### Python

```python
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 ans
```