Queries on Number of Points Inside a Circle — Solution
Queries on Number of Points Inside a Circle solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Queries on Number of Points Inside a Circle is a medium coding problem on arrays, math and geometry, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Arrays, Math, Geometry
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
points[i] = [xi, yi] is a point in the plane; several points may share a position. Each query queries[j] = [xj, yj, rj] describes a circle with centre (xj, yj) and radius rj.
For every query, count the points that lie inside or on its circle. Return the counts as an array answer where answer[j] belongs to queries[j].
Example 1
Input: points = [[0,0],[2,0],[1,1],[3,3]], queries = [[1,0,1],[0,0,3],[5,5,1]]
Output: [3,3,0]
Explanation: The first circle passes exactly through (0,0), (2,0) and (1,1).
Example 2
Input: points = [[4,4],[4,4]], queries = [[4,5,1]]
Output: [2]
Explanation: Both copies of (4,4) lie on the boundary.
Example 3
Input: points = [[10,10]], queries = [[0,0,14],[0,0,15]]
Output: [0,1]
Constraints
1 <= points.length <= 500points[i].length == 20 <= xi, yi <= 5001 <= queries.length <= 500queries[j].length == 30 <= xj, yj <= 5001 <= rj <= 500
Follow-up: Can you answer each query in better than O(n) time?
Hints for Queries on Number of Points Inside a Circle
Hint 1
With at most 500 points and 500 queries, checking every pair is only 250,000 tests.
Hint 2
A point
(x, y)is in the circle when its distance to the centre is at mostr.Hint 3
Compare squared values:
(x - xj)² + (y - yj)² <= rj²keeps everything an exact integer.
How to solve Queries on Number of Points Inside a Circle
Test every point against every circle with an exact integer distance check.
Approach
- For each query
[xj, yj, rj], start a counter at 0. - For each point, compute
dx = x - xj,dy = y - yjand add one ifdx² + dy² <= rj². - Store the counter as
answer[j].
Why it works
A point lies inside or on a circle exactly when its Euclidean distance to the centre is at most the radius; both sides are non-negative, so squaring preserves the comparison. Each point is checked once per query, so every count is exact, and duplicate points are counted as often as they appear.
Complexity
- Time —
O(n · q) - Space —
O(q) for the answer
Pitfalls
- Use
<=— points on the boundary count. - Avoid
sqrt; floating-point rounding can flip boundary points. - For the follow-up, sort points by x and only scan the strip
[xj - rj, xj + rj], or bucket them on a grid.
Reference solution
Python
from typing import List
def countPoints(points: List[List[int]], queries: List[List[int]]) -> List[int]:
answer = []
for qx, qy, r in queries:
rr = r * r
c = 0
for x, y in points:
dx = x - qx
dy = y - qy
if dx * dx + dy * dy <= rr:
c += 1
answer.append(c)
return answerJava
public static int[] countPoints(int[][] points, int[][] queries) {
int[] answer = new int[queries.length];
for (int j = 0; j < queries.length; j++) {
int qx = queries[j][0], qy = queries[j][1], rr = queries[j][2] * queries[j][2];
int c = 0;
for (int[] p : points) {
int dx = p[0] - qx, dy = p[1] - qy;
if (dx * dx + dy * dy <= rr) c++;
}
answer[j] = c;
}
return answer;
}C++
vector<int> countPoints(vector<vector<int>>& points, vector<vector<int>>& queries) {
vector<int> answer;
for (auto& q : queries) {
int rr = q[2] * q[2];
int c = 0;
for (auto& p : points) {
int dx = p[0] - q[0], dy = p[1] - q[1];
if (dx * dx + dy * dy <= rr) c++;
}
answer.push_back(c);
}
return answer;
}JavaScript
var countPoints = function(points, queries) {
var answer = [];
for (var j = 0; j < queries.length; j++) {
var qx = queries[j][0], qy = queries[j][1], rr = queries[j][2] * queries[j][2];
var c = 0;
for (var i = 0; i < points.length; i++) {
var dx = points[i][0] - qx, dy = points[i][1] - qy;
if (dx * dx + dy * dy <= rr) c++;
}
answer.push(c);
}
return answer;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays