Queries on Number of Points Inside a Circle solution and explanation
Google
9 more videos on this problem
Leetcode Medium 1828. Queries on Number of Points Inside a Circle || Biweekly contest 50Code with Alisha · 7:00 · 4K views
LeetCode 1828. Queries on Number of Points Inside a Circle - Interview Prep Ep 120Fisher Coder · 7:32 · 3K views
1828. Queries on Number of Points Inside a Circle (Leetcode Medium)Programming Live with Larry · 4:09 · 579 views
LeetCode 1828: Queries on Number of Points Inside a Circle: Python MediumHashem Alsaket · 3:33 · 498 views
Queries on Number of Points Inside a Circle | LeetCode | Biweekly Contest 50Nalin Goyal · 6:52 · 344 views
LeetCode 1828. [Medium] Queries on Number of Points Inside a CircleFrancesco Manicardi · 3:04 · 196 views
34— Queries on Number of Points Inside a Circle | JavaScriptInformTech · 11:03 · 185 views
LeetCode 1828 | Queries on Number of Points Inside a Circle | Array | JavaSleepy Cracker · 8:46 · 183 views
Queries on Number of Points Inside a Circle LeetCode Q1828 | CodethingsDanny Helou · 7:09 · 180 views
Leetcode Problem 1828 - Queries on Number of Points Inside a CircleBitmask · 6:08 · 160 views
The 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:
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)?
Approach overview
Problem Overview: You receive a list of 2D points and several circular queries. Each query provides a center (x, y) and radius r. For every query, count how many points lie inside or on the circle.
Approach 1: Basic Distance Check (O(n * q) time, O(1) space)
The direct solution checks every point for every query. For a point (px, py) and query center (cx, cy), compute the squared distance: (px - cx)^2 + (py - cy)^2. If this value is less than or equal to r^2, the point lies inside the circle. Using squared distance avoids expensive square root operations and keeps calculations integer based. This approach simply iterates through all points for each query, making it easy to implement and reliable when input sizes are moderate.
The algorithm relies on basic geometry and arithmetic operations on coordinates. Because each query scans the entire list of points, runtime grows linearly with both points and queries. Still, the code stays clean and predictable, which is why this method is commonly accepted in interviews and competitive programming.
Approach 2: Coordinate Binning (≈O(q * k) average time, O(n) space)
When the number of points becomes large, scanning every point per query wastes work. Coordinate binning partitions the 2D plane into buckets (for example, grid cells). Each point is stored in a bucket based on its coordinates. During a query, you only examine buckets that intersect the circle's bounding square rather than the entire dataset.
For each candidate bucket, iterate through the points inside it and perform the same squared distance check used in the basic solution. If the grid size is chosen well, the number of candidate points k remains small relative to the total number of points. This reduces the average amount of work per query significantly.
This strategy is essentially a lightweight spatial index built using arrays or hash maps. It combines ideas from Array processing with geometric filtering from Geometry and numeric calculations from Math.
Recommended for interviews: The basic distance check is usually what interviewers expect. It demonstrates that you understand the geometric condition for a point inside a circle and can implement it efficiently using squared distances. The coordinate binning optimization shows deeper problem solving and awareness of spatial indexing when datasets grow large.
Approach 1: Basic Distance Check
The straightforward approach involves iterating over each query and checking each point to see if it falls within the circle centered at (xj, yj) with radius rj. The condition for a point (xi, yi) to be inside the circle is given by the inequality:
(xi - xj)2 + (yi - yj)2 ≤ rj2
If the condition is true, we count the point as inside the circle.
def countPoints(points, queries):
result = []
for query in queries:
xj, yj, rj = query
count = 0
for point in points:
xi, yi = point
if (xi - xj)**2 + (yi - yj)**2 <= rj**2:
count += 1
result.append(count)
return resultpublic int[] countPoints(int[][] points, int[][] queries) {
int[] result = new int[queries.length];
for (int j = 0; j < queries.length; j++) {
int xj = queries[j][0], yj = queries[j][1], rj = queries[j][2];
int count = 0;
for (int[] point : points) {
int xi = point[0], yi = point[1];
if ((xi - xj) * (xi - xj) + (yi - yj) * (yi - yj) <= rj * rj) {
count++;
}
}
result[j] = count;
}
return result;
}The function iterates over each circle query and for each query, it iterates over every point. It checks if the squared distance from the point to the circle's center is less than or equal to the squared radius of the circle. If true, it increments the count. At the end of each query, it appends the count to the result list.
Time Complexity: O(n*m), where n is the number of points and m is the number of queries.
Space Complexity: O(1), aside from the output list.
Approach 2: Coordinate Binning
This method leverages spatial binning to potentially reduce checks. Divide the plane into grid bins, and store points in these bins. For each query circle, calculate the bins that the circle can encompass and only check the points in these bins. This may not improve worst-case complexity but can optimize average performance for sparse points.
def countPoints(points, queries):
from collections import defaultdict
import math
# Create a defaultdict to hold points by bin
bins = defaultdict(list)
bin_size = 10
# Populate the bins
for x, y in points:
bins[(x // bin_size, y // bin_size)].append((x, y))
result = []
for xj, yj, rj in queries:
count = 0
radius_squared = rj * rj
# Calculate bin range this circle could affect
min_bin_x = (xj - rj) // bin_size
max_bin_x = (xj + rj) // bin_size
min_bin_y = (yj - rj) // bin_size
max_bin_y = (yj + rj) // bin_size
for bx in range(min_bin_x, max_bin_x + 1):
for by in range(min_bin_y, max_bin_y + 1):
if (bx, by) in bins:
for px, py in bins[(bx, by)]:
if (px - xj) ** 2 + (py - yj) ** 2 <= radius_squared:
count += 1
result.append(count)
return resultThis solution first bins the points by dividing the coordinate plane into grids. For each query, it calculates which bins might intersect with the circle and only checks points in those bins. This approach reduces the number of distance calculations needed when there are multiple queries over dense areas.
Time Complexity: Average-case can be better than O(n*m) in sparse distributions due to reduced distance checks.
Space Complexity: O(n) for storing points in bins.
Approach 3: Enumeration
Enumerate all the circles (x, y, r). For each circle, calculate the number of points within the circle to get the answer.
The time complexity is O(m times n), where m and n are the lengths of the arrays queries and points respectively. Ignoring the space consumption of the answer, the space complexity is O(1).
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;
}
};function countPoints(points: number[][], queries: number[][]): number[] {
return queries.map(([cx, cy, r]) => {
let res = 0;
for (const [px, py] of points) {
if (Math.sqrt((cx - px) ** 2 + (cy - py) ** 2) <= r) {
res++;
}
}
return res;
});
}/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* countPoints(int** points, int pointsSize, int* pointsColSize, int** queries, int queriesSize, int* queriesColSize,
int* returnSize) {
int* ans = malloc(sizeof(int) * queriesSize);
for (int i = 0; i < queriesSize; i++) {
int cx = queries[i][0];
int cy = queries[i][1];
int r = queries[i][2];
int count = 0;
for (int j = 0; j < pointsSize; j++) {
if (sqrt(pow(points[j][0] - cx, 2) + pow(points[j][1] - cy, 2)) <= r) {
count++;
}
}
ans[i] = count;
}
*returnSize = queriesSize;
return ans;
}func countPoints(points [][]int, queries [][]int) (ans []int) {
for _, q := range queries {
x, y, r := q[0], q[1], q[2]
cnt := 0
for _, p := range points {
i, j := p[0], p[1]
dx, dy := i-x, j-y
if dx*dx+dy*dy <= r*r {
cnt++
}
}
ans = append(ans, cnt)
}
return
}impl Solution {
pub fn count_points(points: Vec<Vec<i32>>, queries: Vec<Vec<i32>>) -> Vec<i32> {
queries
.iter()
.map(|v| {
let cx = v[0];
let cy = v[1];
let r = v[2].pow(2);
let mut count = 0;
for p in points.iter() {
if (p[0] - cx).pow(2) + (p[1] - cy).pow(2) <= r {
count += 1;
}
}
count
})
.collect()
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Basic Distance Check | Time Complexity: O(n*m), where n is the number of points and m is the number of queries. |
| Coordinate Binning | Time Complexity: Average-case can be better than O(n*m) in sparse distributions due to reduced distance checks. |
| Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Basic Distance Check | O(n * q) | O(1) | General case and typical interview solution when constraints are moderate |
| Coordinate Binning | ≈O(q * k) average | O(n) | Large datasets where reducing candidate points per query improves performance |
Frequently asked questions
Is Queries on Number of Points Inside a Circle easy or hard?
The problem is rated Medium but conceptually straightforward. The challenge is recognizing that square root operations are unnecessary and that comparing squared distances is enough to determine whether a point lies inside the circle.
Queries on Number of Points Inside a Circle Python/Java solution
Both Python and Java implementations typically loop through the points for each query and compute squared distances. The logic stays the same across languages: subtract coordinates, square the differences, sum them, and compare with the squared radius.
How to solve Queries on Number of Points Inside a Circle in O(n)?
Strict O(n) for all queries is not typical because each query may require checking multiple points. However, spatial partitioning techniques such as coordinate binning or grid bucketing reduce the number of candidate points per query. With good bucket sizing, the average runtime approaches O(q * k), where k is the number of nearby points.
What is the best approach for Queries on Number of Points Inside a Circle?
The most common approach checks each point against every query using the circle distance formula. Compute the squared distance (px - cx)^2 + (py - cy)^2 and compare it with r^2. This runs in O(n * q) time with O(1) extra space and is usually sufficient for typical constraints.
Is Queries on Number of Points Inside a Circle asked at Google/Amazon/Meta?
Geometry and spatial query problems like this appear in technical interviews at large companies including Google, Amazon, and Meta. The focus is usually on recognizing the distance formula and implementing efficient point filtering using squared distances.
What data structure is used in Queries on Number of Points Inside a Circle?
The basic implementation uses arrays to store points and queries. Optimized solutions may use hash maps or grid buckets to group coordinates, which acts as a simple spatial index that reduces the number of distance checks per query.
What is the time complexity of Queries on Number of Points Inside a Circle?
The straightforward solution runs in O(n * q) time, where n is the number of points and q is the number of queries. Each query scans all points and performs a constant time distance calculation. Space complexity remains O(1) since no additional structures are required.