#1828

Medium

LeetCode Problem Workspace

Queries on Number of Points Inside a Circle

Determine how many 2D points lie within multiple circles using array iteration and Euclidean distance calculations efficiently.

array math geometry

Problem Statement

You are given a list of points on a 2D plane, where each point is represented by its coordinates [x, y]. Multiple points may share the same coordinates. Additionally, you have a set of circle queries, each described by its center [x, y] and radius r.

For every circle query, determine the number of points that lie inside or on the border of the circle. Return an array where each element corresponds to the count of points inside the respective circle query. Points exactly on the circle edge are included in the count.

Examples

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]

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]

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 <= 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.

Solution Approach

Iterate and Compute Distances

Loop through each circle query, and for each query, iterate over all points. Compute the squared Euclidean distance between the point and the circle center and compare it with the radius squared to decide if the point is inside.

Avoid Floating Point Errors

Use squared distances instead of square roots to prevent floating point inaccuracies. This ensures points exactly on the circle border are counted correctly without rounding errors.

Optimize with Early Filtering

If needed, pre-filter points by their x and y coordinates to skip points that are obviously outside the bounding box of the circle. This reduces unnecessary distance calculations for large datasets within constraints.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n * m), where n is the number of points and m is the number of queries, because each point may be checked against every circle. Space complexity is O(m) for the result array, with no additional significant memory usage.

What Interviewers Usually Probe

Are you handling points exactly on the circle boundary correctly?
Can you optimize distance computations to avoid square root operations?
How would this approach scale if the number of points or queries increased?

Common Pitfalls or Variants

Common pitfalls

Using floating point square roots can miscount points on the border.
Forgetting to include points exactly at the circle's radius in the count.
Assuming all points are unique and skipping duplicates incorrectly.

Follow-up variants

Counting points inside rectangles instead of circles using array iteration.
Finding the closest point to each circle center instead of counting all points.
Handling 3D points and spherical queries with the same distance check logic.

FAQ

What is the core pattern in Queries on Number of Points Inside a Circle?

The problem relies on the array plus math pattern: iterating points and using Euclidean distance to count points inside each circle.

Do points on the circle edge count as inside?

Yes, any point with a distance equal to or less than the radius is considered inside the circle.

Can I optimize by pre-sorting points?

Sorting may help if you use spatial filtering or bounding box checks, but basic iteration suffices within the problem constraints.

Why use squared distances instead of actual distance?

Squared distances avoid floating point errors and unnecessary square root calculations, ensuring accurate counts for points on borders.

What is the expected output format?

Return an array of integers, where each element represents the number of points inside the corresponding circle query.

terminal

Solution

Solution 1: Enumeration

Enumerate all the circles $(x, y, r)$. For each circle, calculate the number of points within the circle to get the answer.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def countPoints(
        self, points: List[List[int]], queries: List[List[int]]
    ) -> List[int]:
        ans = []
        for x, y, r in queries:
            cnt = 0
            for i, j in points:
                dx, dy = i - x, j - y
                cnt += dx * dx + dy * dy <= r * r
            ans.append(cnt)
        return ans

Continue Practicing

#1610 maximum number of visible points #2101 detonate the maximum bombs #1515 best position for a service centre