Queries on Number of Points Inside a Circle: Distance Check Pattern

You are given an array points where points[i] = [xi, yi] represents a point on a 2D plane, and an array queries where queries[j] = [xj, yj, rj] describes a circle centered at (xj, yj) with radius rj. For each query, return the number of points that are inside or on the border of the circle. That is LeetCode 1828: Queries on Number of Points Inside a Circle.

Example: points = [[1,3],[3,3],[5,3],[2,2]], queries = [[2,3,1],[4,3,1],[1,1,2]] returns [3,2,2]. For the first query circle centered at (2,3) with radius 1, three points fall inside or on the boundary.

Why this problem matters

This problem tests whether you can translate a geometric condition into clean code. The math is simple (Euclidean distance), but the implementation details trip people up. Using floating-point sqrt introduces precision bugs. The squared-distance trick avoids that entirely, and it is a pattern you will reuse in many geometry and proximity problems.

It also reinforces the brute-force-is-fine instinct. Not every problem needs a clever data structure. When the constraints are small enough, a nested loop with the right math is the best solution.

Key insight

A point (px, py) lies inside or on a circle with center (cx, cy) and radius r when:

(px - cx)^2 + (py - cy)^2 <= r^2

By comparing squared distances, you avoid calling sqrt altogether. This eliminates floating-point precision issues and is faster. Both sides of the inequality are integers when the inputs are integers, so the comparison is exact.

The solution

def count_points(points: list[list[int]], queries: list[list[int]]) -> list[int]:
    result = []
    for cx, cy, r in queries:
        r_sq = r * r
        count = 0
        for px, py in points:
            dx, dy = px - cx, py - cy
            if dx * dx + dy * dy <= r_sq:
                count += 1
        result.append(count)
    return result

Walkthrough of the code

Outer loop over queries: For each query, you extract the center coordinates (cx, cy) and radius r. You precompute r_sq = r * r once per query so you do not recompute it for every point.

Inner loop over points: For each point (px, py), compute the horizontal distance dx = px - cx and vertical distance dy = py - cy. The squared Euclidean distance is dx * dx + dy * dy. If this value is at most r_sq, the point is inside or on the circle boundary, so you increment the count.

Building the result: After scanning all points for a query, append the count to the result list. The output array has one entry per query, in the same order as the queries.

Visual walkthrough

Let's trace through all three queries with points = [[1,3],[3,3],[5,3],[2,2]].

For each query, you loop through every point and check the squared distance. No sorting, no preprocessing, just direct comparison.

Complexity analysis

Time: You process q queries, and for each query you check all n points. Each check is O(1) arithmetic. Total: O(q * n).

Space: The only extra space is the result array of length q. The input arrays are not modified. Total: O(q).

The building blocks

This problem is built on two reusable pieces that CodeBricks drills independently:

Squared Euclidean distance check

The pattern of computing squared distance between two points and comparing against a squared threshold:

dx, dy = px - cx, py - cy
if dx * dx + dy * dy <= r_sq:
    ...

This is the fundamental proximity test in 2D geometry. You will see it in problems like K Closest Points to Origin (sort by squared distance), circle-circle intersection tests, and any problem where you need to decide whether a point is "close enough" to a reference. The key is to never take the square root. Squaring preserves the ordering, and you avoid precision issues entirely.

Linear scan with per-query accumulation

The pattern of iterating through all elements for each query and accumulating a count:

for query in queries:
    count = 0
    for item in items:
        if condition(item, query):
            count += 1
    result.append(count)

This structure appears whenever you have multiple independent queries against the same dataset and each query needs an aggregate. Range sum queries (before prefix sums), voting tallies, and filter-and-count problems all use this template. When the dataset is small or the queries cannot be batched efficiently, this brute-force pattern is the right choice.

Edge cases

• Point exactly on the boundary: When the squared distance equals r^2 exactly, the point counts as inside. The problem statement says "inside or on the border," so use <= not <.
• Radius zero: A circle with radius 0 is just a single point. Only points that match the center coordinates exactly will have squared distance 0, so they count. The code handles this without special cases.
• All points inside: If every point falls inside a query circle, the count equals n. No early termination is needed since you still check all points.
• No points inside: If no point satisfies the distance check, the count is 0. The code naturally produces this.
• Overlapping queries: Each query is independent. Two queries might cover the same points, and that is fine. You count fresh for each query.

From understanding to recall

You have seen how a simple squared-distance check solves every query. The algorithm is only a handful of lines, but the details matter: precomputing r_sq, using <= for boundary inclusion, and avoiding sqrt. Under time pressure, it is easy to reach for math.sqrt and introduce precision bugs.

Spaced repetition locks it in. You practice writing the squared-distance comparison, the nested-loop structure, and the boundary condition from scratch. Do it today, again in two days, again in five. After a few reps, you see "points inside a circle" and the distance-check pattern writes itself.

The squared-distance check and per-query linear scan are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Rectangle Area - Geometry calculations with coordinate math
• Max Points on a Line - Point geometry and distance relationships
• K Closest Points to Origin - Distance-based point problems

CodeBricks breaks Queries on Number of Points Inside a Circle into its squared-distance check and per-query accumulation building blocks, then drills them independently with spaced repetition. You type the distance formula, the nested-loop structure, and the boundary condition from scratch until the pattern is automatic. When a geometry or proximity problem shows up in your interview, you do not think about it. You just write it.