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
Follow up: Could you find the answer for each query in better complexity than O(n)?
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.
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.
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.
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.
This 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.
Python
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.
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).
| 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 | — |
| 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 |
Leetcode Medium 1828. Queries on Number of Points Inside a Circle || Biweekly contest 50 • Code with Alisha • 4,299 views views
Watch 9 more video solutions →Practice Queries on Number of Points Inside a Circle with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor