LeetCode 1828 - Queries on Number of Points Inside a Circle

Difficulty: 🟡 Medium
Topics: Array, Math, Geometry

Solution

Problem Understanding

This problem gives us two collections of geometric objects on a 2D plane.

The first collection is an array called points, where each element is a coordinate pair [x, y]. Each pair represents a point on the plane. Multiple points are allowed to have the exact same coordinates, so duplicates must be counted separately.

The second collection is an array called queries. Each query is represented as [x, y, r], where:

(x, y) is the center of a circle
r is the radius of that circle

For every query, we must determine how many points lie inside or on the boundary of the circle.

A point (px, py) is inside a circle centered at (cx, cy) with radius r if:

$$(px - cx)^2 + (py - cy)^2 \le r^2$$

The left side represents the squared Euclidean distance between the point and the center. The right side is the squared radius. Using squared values avoids floating point operations and square roots.

The output is an array where each element corresponds to one query. For each circle, we return the number of points that satisfy the distance condition.

The constraints are relatively small:

At most 500 points
At most 500 queries

This means there are at most:

$$500 \times 500 = 250000$$

point-query comparisons.

That is small enough for a direct simulation approach to pass comfortably.

Several edge cases are important:

Points exactly on the circle boundary must be counted.
Multiple points may share identical coordinates and must all be counted.
Radius values can be large enough to include all points.
Queries may contain circles with no points inside.
Coordinates are non-negative integers, but distance computations can still grow large enough that using squared distances is safer than using floating point square roots.

Approaches

Brute Force Approach

The most direct solution is to process every query independently.

For each query:

Extract the circle center and radius.
Iterate through every point.
Compute the squared distance from the point to the circle center.
If the squared distance is less than or equal to the squared radius, count the point.

This works because the definition of a point being inside a circle depends only on its distance from the center.

Since every query checks every point exactly once, the total complexity is:

$$O(q \times n)$$

where:

q is the number of queries
n is the number of points

Given the constraints, this is completely acceptable.

Better Insight

The follow up asks whether we can answer queries in better than O(n) time.

For larger constraints, we could consider spatial indexing structures such as:

Quad trees
KD-trees
Grid bucketing
Prefix sum techniques over coordinates

However, for this problem's constraints, such optimizations are unnecessary and would only complicate the implementation.

The key insight is that the input size is small enough that a carefully implemented brute force solution is already optimal in practice.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(q × n)	O(1) extra	Check every point for every query
Spatial Indexing Optimization	Better than O(n) per query	O(n) or more	Useful only for much larger inputs

Algorithm Walkthrough

Optimal Algorithm

Create an empty result array.

We will store the answer for each query in this array. 2. Iterate through each query.

Each query contains:

centerX
centerY
radius

Compute the squared radius.

Instead of using square roots, compute:

$$radiusSquared = radius \times radius$$

This keeps all calculations in integers and avoids floating point precision issues. 4. Initialize a counter for the current query.

This counter tracks how many points lie inside or on the circle. 5. Iterate through every point.

For each point:

Compute the horizontal difference:

$$dx = pointX - centerX$$

Compute the vertical difference:

$$dy = pointY - centerY$$ 6. Compute the squared distance.

Use:

$$distanceSquared = dx^2 + dy^2$$ 7. Compare the squared distance with the squared radius.

If:

$$distanceSquared \le radiusSquared$$

then the point is inside or on the boundary of the circle, so increment the counter. 8. After checking all points, append the counter to the result array. 9. Return the result array after processing all queries.

Why it works

The Euclidean distance formula determines whether a point lies inside a circle. Instead of comparing actual distances, we compare squared distances:

$$(px - cx)^2 + (py - cy)^2 \le r^2$$

This condition is mathematically equivalent to the standard circle equation and correctly includes boundary points because of the <= comparison.

Since every query checks every point exactly once, every valid point is counted and no invalid point is included.

Python Solution

from typing import List

class Solution:
    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:
        answer = []

        for center_x, center_y, radius in queries:
            radius_squared = radius * radius
            count = 0

            for point_x, point_y in points:
                dx = point_x - center_x
                dy = point_y - center_y

                distance_squared = dx * dx + dy * dy

                if distance_squared <= radius_squared:
                    count += 1

            answer.append(count)

        return answer

The implementation follows the algorithm directly.

The outer loop processes each query independently. For each query, the code extracts the center coordinates and radius.

The radius is squared once before checking points. This avoids recomputing radius * radius repeatedly.

The inner loop iterates through every point. For each point, the code computes the horizontal and vertical offsets from the circle center.

Using these offsets, the squared distance is computed with:

dx * dx + dy * dy

If this value is less than or equal to the squared radius, the point lies inside or on the boundary of the circle, so the counter is incremented.

After all points are processed for a query, the count is appended to the result list.

Finally, the method returns the completed answer array.

Go Solution

func countPoints(points [][]int, queries [][]int) []int {
    answer := make([]int, 0, len(queries))

    for _, query := range queries {
        centerX := query[0]
        centerY := query[1]
        radius := query[2]

        radiusSquared := radius * radius
        count := 0

        for _, point := range points {
            dx := point[0] - centerX
            dy := point[1] - centerY

            distanceSquared := dx*dx + dy*dy

            if distanceSquared <= radiusSquared {
                count++
            }
        }

        answer = append(answer, count)
    }

    return answer
}

The Go implementation mirrors the Python solution closely.

Slices are used for both the input and output arrays. The result slice is initialized with capacity equal to the number of queries to avoid unnecessary reallocations.

All computations use integers, which is safe because the maximum coordinate difference is small. Integer overflow is not a concern under the given constraints.

Unlike Python, Go requires explicit variable declarations and uses := for local variable initialization.

Worked Examples

Example 1

Input:

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

Query 1: `[2,3,1]`

Circle center:

(2,3)

Radius squared:

1^2 = 1

Point	dx	dy	Distance Squared	Inside?
(1,3)	-1	0	1	Yes
(3,3)	1	0	1	Yes
(5,3)	3	0	9	No
(2,2)	0	-1	1	Yes

Answer for this query:

Query 2: `[4,3,1]`

Radius squared:

Point	dx	dy	Distance Squared	Inside?
(1,3)	-3	0	9	No
(3,3)	-1	0	1	Yes
(5,3)	1	0	1	Yes
(2,2)	-2	-1	5	No

Answer:

Query 3: `[1,1,2]`

Radius squared:

Point	dx	dy	Distance Squared	Inside?
(1,3)	0	2	4	Yes
(3,3)	2	2	8	No
(5,3)	4	2	20	No
(2,2)	1	1	2	Yes

Answer:

Final output:

[3,2,2]

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]]

Query 1: `[1,2,2]`

Radius squared:

Point	Distance Squared	Inside?
(1,1)	1	Yes
(2,2)	1	Yes
(3,3)	5	No
(4,4)	13	No
(5,5)	25	No

Count:

Query 2: `[2,2,2]`

Radius squared:

Point	Distance Squared	Inside?
(1,1)	2	Yes
(2,2)	0	Yes
(3,3)	2	Yes
(4,4)	8	No
(5,5)	18	No

Count:

Query 3: `[4,3,2]`

Radius squared:

Point	Distance Squared	Inside?
(1,1)	13	No
(2,2)	5	No
(3,3)	1	Yes
(4,4)	1	Yes
(5,5)	5	No

Count:

Query 4: `[4,3,3]`

Radius squared:

Point	Distance Squared	Inside?
(1,1)	13	No
(2,2)	5	Yes
(3,3)	1	Yes
(4,4)	1	Yes
(5,5)	5	Yes

Count:

Final output:

[2,3,2,4]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(q × n)	Each query checks every point once
Space	O(1) extra	Only a few variables are used besides the output

The algorithm uses two nested loops:

One loop over all queries
One loop over all points

Therefore, the total number of operations is proportional to:

$$queries.length \times points.length$$

The problem constraints are small enough that this approach runs efficiently.

The space complexity is constant if we exclude the output array, because only a few integer variables are maintained during computation.

Test Cases

from typing import List

class Solution:
    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:
        answer = []

        for center_x, center_y, radius in queries:
            radius_squared = radius * radius
            count = 0

            for point_x, point_y in points:
                dx = point_x - center_x
                dy = point_y - center_y

                if dx * dx + dy * dy <= radius_squared:
                    count += 1

            answer.append(count)

        return answer

solution = Solution()

# Example 1
assert solution.countPoints(
    [[1,3],[3,3],[5,3],[2,2]],
    [[2,3,1],[4,3,1],[1,1,2]]
) == [3,2,2]  # standard mixed example

# Example 2
assert solution.countPoints(
    [[1,1],[2,2],[3,3],[4,4],[5,5]],
    [[1,2,2],[2,2,2],[4,3,2],[4,3,3]]
) == [2,3,2,4]  # multiple overlapping circles

# Single point exactly on boundary
assert solution.countPoints(
    [[3,0]],
    [[0,0,3]]
) == [1]  # boundary points count as inside

# Single point outside circle
assert solution.countPoints(
    [[4,0]],
    [[0,0,3]]
) == [0]  # point outside radius

# Duplicate points
assert solution.countPoints(
    [[1,1],[1,1],[1,1]],
    [[1,1,1]]
) == [3]  # duplicates counted separately

# Large radius includes all points
assert solution.countPoints(
    [[0,0],[100,100],[500,500]],
    [[250,250,1000]]
) == [3]  # huge circle covers everything

# No points inside
assert solution.countPoints(
    [[10,10],[20,20]],
    [[0,0,5]]
) == [0]  # empty result for query

# Multiple queries on same points
assert solution.countPoints(
    [[1,2],[2,3],[3,4]],
    [[0,0,1],[2,3,1],[10,10,20]]
) == [0,3,3]  # varying circle sizes

# Minimum radius
assert solution.countPoints(
    [[0,1],[1,0],[0,0]],
    [[0,0,1]]
) == [3]  # radius one includes adjacent axis points

# Maximum coordinate values
assert solution.countPoints(
    [[500,500]],
    [[500,500,1]]
) == [1]  # upper coordinate boundary

Test Summary

Test	Why
Example 1	Verifies standard functionality
Example 2	Verifies multiple overlapping circles
Boundary point	Ensures border points are counted
Outside point	Ensures invalid points are excluded
Duplicate points	Confirms duplicates are counted separately
Large radius	Tests circles covering all points
No points inside	Tests zero-count queries
Multiple queries	Verifies independent query handling
Minimum radius	Tests smallest valid radius
Maximum coordinates	Tests upper constraint limits

Edge Cases

Points on the Circle Boundary

A common mistake is using a strict inequality:

distance_squared < radius_squared

instead of:

distance_squared <= radius_squared

The problem explicitly states that boundary points are considered inside the circle. The implementation handles this correctly with the <= comparison.

Duplicate Points

The input allows multiple identical points. A buggy implementation might attempt to deduplicate points using a set or hash structure, which would produce incorrect counts.

The algorithm processes every point independently, so duplicates are naturally counted multiple times.

Very Large Circles

Some queries may have radii large enough to include every point. The implementation still works correctly because every point is checked independently against the distance formula.

Since coordinates are capped at 500, squared distance values remain small and safe for integer arithmetic.

Queries with No Matching Points

A query may describe a circle far away from all points. In that case, the count should remain zero.

The implementation initializes the counter to zero for every query and only increments when a point satisfies the condition, so empty results are handled naturally.

Integer Arithmetic vs Floating Point Arithmetic

Using square roots introduces unnecessary floating point computations and possible precision issues.

The implementation compares squared distances instead:

$$dx^2 + dy^2 \le r^2$$

This is mathematically equivalent and guarantees exact integer comparisons.

LeetCode 1828 - Queries on Number of Points Inside a Circle

Solution

Problem Understanding

Approaches

Brute Force Approach

Better Insight

Approach Comparison

Algorithm Walkthrough

Optimal Algorithm

Why it works

Python Solution

Go Solution

Worked Examples

Example 1

Query 1: [2,3,1]

Query 2: [4,3,1]

Query 3: [1,1,2]

Example 2

Query 1: [1,2,2]

Query 2: [2,2,2]

Query 3: [4,3,2]

Query 4: [4,3,3]

Complexity Analysis

Test Cases

Test Summary

Edge Cases

Points on the Circle Boundary

Duplicate Points

Very Large Circles

Queries with No Matching Points

Integer Arithmetic vs Floating Point Arithmetic

Query 1: `[2,3,1]`

Query 2: `[4,3,1]`

Query 3: `[1,1,2]`

Query 1: `[1,2,2]`

Query 2: `[2,2,2]`

Query 3: `[4,3,2]`

Query 4: `[4,3,3]`