1828. Queries on Number of Points Inside a Circle
Asked at Anduril
Difficulty
Medium
Time
O(p * q)
Space
O(q)
Pattern
Array
Companies
1
Problem
You are given a list of points on a 2D plane, where points[i] = [xi, yi]. Several points may share the same coordinates.
You are also given a list of circles, where queries[j] = [xj, yj, rj] means a circle centered at (xj, yj) with radius rj. For every circle, count how many points lie inside it or exactly on its border.
Return an array answer where answer[j] is the count for the j-th circle. The order of the answers must match the order of the queries.
A point (px, py) is inside circle (x, y, r) when (px - x)² + (py - y)² <= r². Compare squared distances, not distances. That avoids square roots and keeps everything in integers, so border points are never misjudged by floating-point rounding.
Count points inside each circle
Constraints
- ●
1 <= points.length <= 500 - ●
points[i].length == 2 - ●
0 <= xi, yi <= 500 - ●
1 <= queries.length <= 500 - ●
queries[j].length == 3 - ●
0 <= xj, yj <= 500 - ●
1 <= rj <= 500 - ●
All coordinates are integers.
Examples
points = [[1,3],[3,3],[5,3],[2,2]], queries = [[2,3,1],[4,3,1],[1,1,2]][3,2,2]points = [[1,1],[2,2],[3,3],[4,4],[5,5]], queries = [[1,2,2],[2,2,2],[4,3,2],[4,3,3]][2,3,2,4]Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Anduril | Medium | View all Anduril questions → |
How to Think About It
A point (px, py) is inside or on the circle iff (px - x)² + (py - y)² <= r².
Compare squared distances. Taking a square root is slower and can misclassify boundary points due to floating-point error.
For each query, loop over all points and count the ones that pass the check: O(points * queries) = 250,000 checks at most.
Follow-up (if the interviewer asks about scale): sort points by x and only check those with x - r <= px <= x + r, or use a spatial grid/k-d tree.
Walkthrough: point (1,3), circle (2,3,1): (1-2)² + 0 = 1 <= 1 -> on the boundary, counted.
Optimal Approach
Step 1: For each query (x, y, r):
cnt = number of points with (px - x)² + (py - y)² <= r².
Append cnt.
Step 2: Return the counts.
Time: O(p * q). Space: O(q) for the output.
Squared distance test
What Trips People Up in Real Interviews
Using sqrt and floating-point comparisons. Squared integer distances are exact.
Using < instead of <= — points on the boundary count.
Over-engineering a spatial index for 500 points. Mention it as a follow-up for larger inputs.
Mixing up which array holds circles and which holds points.
Solution Code
O(p * q) timedef countPoints(points, queries):
res = []
for x, y, r in queries:
r2 = r * r
cnt = 0
for px, py in points:
if (px - x) ** 2 + (py - y) ** 2 <= r2:
cnt += 1
res.append(cnt)
return resFrequently Asked Questions
What is the Queries on Number of Points Inside a Circle problem?
Queries on Number of Points Inside a Circle gives you points and circle queries `(x, y, r)`, and asks, for each circle, how many points lie inside or on it. With at most 500 points and 500 queries, a direct check per pair is the intended solution — the interview value is in doing the geometry cleanly with integers.
How do you solve Queries on Number of Points Inside a Circle?
The optimal approach runs in O(p * q) time and O(q) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Queries on Number of Points Inside a Circle?
Queries on Number of Points Inside a Circle is asked at Anduril. It is a medium difficulty problem.
What are common mistakes on Queries on Number of Points Inside a Circle?
- Using `sqrt` and floating-point comparisons. Squared integer distances are exact.
- Using `<` instead of `<=` — points on the boundary count.
- Over-engineering a spatial index for 500 points. Mention it as a follow-up for larger inputs.
- Mixing up which array holds circles and which holds points.