Skip to main content
Talentd

Queries on Number of Points Inside a Circle - Solution & Explanation

MediumArrayMathGeometry11 min readAsked at: Google, Anduril
Practice this problem

Problem Statement

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 <= 500
  • points[i].length == 2
  • 0 <= xā€‹ā€‹ā€‹ā€‹ā€‹ā€‹i, yā€‹ā€‹ā€‹ā€‹ā€‹ā€‹i <= 500
  • 1 <= queries.length <= 500
  • queries[j].length == 3
  • 0 <= xj, yj <= 500
  • 1 <= rj <= 500
  • All coordinates are integers.

 

Follow up: Could you find the answer for each query in better complexity than O(n)?

Approach Overview

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.

Approach 1: Basic Distance Check

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.

Code

PythonJava

Python

Java

Complexity

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.

Try this approach in the editor ā†’

Approach 2: Coordinate Binning

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.

Code

Python

Python

Complexity

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.

Try this approach in the editor ā†’

Approach 3: Enumeration

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

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor ā†’

Complexity Comparison

ApproachComplexity
Basic Distance Check

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.

Coordinate Binning

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.

Enumerationā€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Basic Distance CheckO(n * q)O(1)General case and typical interview solution when constraints are moderate
Coordinate Binningā‰ˆO(q * k) averageO(n)Large datasets where reducing candidate points per query improves performance

Video Solution

Leetcode Medium 1828. Queries on Number of Points Inside a Circle || Biweekly contest 50 ā€¢ Code with Alisha ā€¢ 4,329 views views

Watch 9 more video solutions ā†’

Frequently Asked Questions

Is Queries on Number of Points Inside a Circle easy or hard?
The problem is rated Medium but conceptually straightforward. The challenge is recognizing that square root operations are unnecessary and that comparing squared distances is enough to determine whether a point lies inside the circle.
Queries on Number of Points Inside a Circle Python/Java solution
Both Python and Java implementations typically loop through the points for each query and compute squared distances. The logic stays the same across languages: subtract coordinates, square the differences, sum them, and compare with the squared radius.
How to solve Queries on Number of Points Inside a Circle in O(n)?
Strict O(n) for all queries is not typical because each query may require checking multiple points. However, spatial partitioning techniques such as coordinate binning or grid bucketing reduce the number of candidate points per query. With good bucket sizing, the average runtime approaches O(q * k), where k is the number of nearby points.
What is the best approach for Queries on Number of Points Inside a Circle?
The most common approach checks each point against every query using the circle distance formula. Compute the squared distance (px - cx)^2 + (py - cy)^2 and compare it with r^2. This runs in O(n * q) time with O(1) extra space and is usually sufficient for typical constraints.
Is Queries on Number of Points Inside a Circle asked at Google/Amazon/Meta?
Geometry and spatial query problems like this appear in technical interviews at large companies including Google, Amazon, and Meta. The focus is usually on recognizing the distance formula and implementing efficient point filtering using squared distances.
What data structure is used in Queries on Number of Points Inside a Circle?
The basic implementation uses arrays to store points and queries. Optimized solutions may use hash maps or grid buckets to group coordinates, which acts as a simple spatial index that reduces the number of distance checks per query.
What is the time complexity of Queries on Number of Points Inside a Circle?
The straightforward solution runs in O(n * q) time, where n is the number of points and q is the number of queries. Each query scans all points and performs a constant time distance calculation. Space complexity remains O(1) since no additional structures are required.

Ready to solve this problem?

Practice Queries on Number of Points Inside a Circle with our built-in code editor and test cases.

Practice on FleetCode
Previous

Check if the Rectangle Corner Is Reachable

Next

Count Lattice Points Inside a Circle