Queries on Number of Points Inside a Circle

For each query, count points within radius — brute force with squared distance is fast enough.

Medium
Time O(n * q) Space O(q)
LeetCode
3 min read
geometry brute-force

Problem#

For each query (qx, qy, r), count how many of the given points lie within (and including the boundary of) the circle centered at (qx, qy) with radius r.

Examples#

  • points=[[1,3],[3,3],[5,3],[2,2]], queries=[[2,3,1],[4,3,1],[1,1,2]][3,2,2].

Constraints#

  • 1 <= points.length, queries.length <= 500, coords in [0, 500], 1 <= r <= 500.

Approach#

Brute force: for each query, scan all points and check (dx*dx + dy*dy) <= r*r. n * q = 250000 ops — well within budget.

Solution#

Queries on Number of Points Inside a Circle
class Solution {
public:
vector<int> countPoints(vector<vector<int>>& points, vector<vector<int>>& queries) {
vector<int> ans;
ans.reserve(queries.size());
for (auto& q : queries) {
int qx = q[0], qy = q[1], r2 = q[2] * q[2], cnt = 0;
for (auto& p : points) {
int dx = p[0] - qx, dy = p[1] - qy;
if (dx*dx + dy*dy <= r2) ++cnt;
}
ans.push_back(cnt);
}
return ans;
}
};

Editorial#

Squared distances dodge floating point entirely. With both n, q <= 500, brute force is the right call — any preprocessing structure (k-d tree, range tree) costs more than the savings.

Complexity#

  • Time: O(n * q).
  • Space: O(q).

Concept revision#

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.