Queries on Number of Points Inside a Circle

Medium
1305.

Queries on Number of Points Inside a Circle

Queries on Number of Points Inside a Circle is a medium coding problem on arrays, math and geometry, asked in Amazon, Google and Microsoft interviews.

points[i] = [xi, yi] is a point in the plane; several points may share a position. Each query queries[j] = [xj, yj, rj] describes a circle with centre (xj, yj) and radius rj.

For every query, count the points that lie inside or on its circle. Return the counts as an array answer where answer[j] belongs to queries[j].

Example 1

Input
points = [[0,0],[2,0],[1,1],[3,3]], queries = [[1,0,1],[0,0,3],[5,5,1]]
Output
[3,3,0]
Explanation
The first circle passes exactly through (0,0), (2,0) and (1,1).

Example 2

Input
points = [[4,4],[4,4]], queries = [[4,5,1]]
Output
[2]
Explanation
Both copies of (4,4) lie on the boundary.

Example 3

Input
points = [[10,10]], queries = [[0,0,14],[0,0,15]]
Output
[0,1]

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

Follow-up: Can you answer each query in better than O(n) time?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} points
 * @param {number[][]} queries
 * @return {number[]}
 */
var countPoints = function(points, queries) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Queries on Number of Points Inside a Circle — Solution

Queries on Number of Points Inside a Circle solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Queries on Number of Points Inside a Circle is a medium coding problem on arrays, math and geometry, asked in Amazon, Google and Microsoft interviews.

  • Difficulty: Medium
  • Topics: Arrays, Math, Geometry
  • Asked at: Amazon, Google, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

points[i] = [xi, yi] is a point in the plane; several points may share a position. Each query queries[j] = [xj, yj, rj] describes a circle with centre (xj, yj) and radius rj.

For every query, count the points that lie inside or on its circle. Return the counts as an array answer where answer[j] belongs to queries[j].

Example 1

Input: points = [[0,0],[2,0],[1,1],[3,3]], queries = [[1,0,1],[0,0,3],[5,5,1]]
Output: [3,3,0]
Explanation: The first circle passes exactly through (0,0), (2,0) and (1,1).

Example 2

Input: points = [[4,4],[4,4]], queries = [[4,5,1]]
Output: [2]
Explanation: Both copies of (4,4) lie on the boundary.

Example 3

Input: points = [[10,10]], queries = [[0,0,14],[0,0,15]]
Output: [0,1]

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

Follow-up: Can you answer each query in better than O(n) time?

Hints for Queries on Number of Points Inside a Circle

  1. Hint 1

    With at most 500 points and 500 queries, checking every pair is only 250,000 tests.

  2. Hint 2

    A point (x, y) is in the circle when its distance to the centre is at most r.

  3. Hint 3

    Compare squared values: (x - xj)² + (y - yj)² <= rj² keeps everything an exact integer.

How to solve Queries on Number of Points Inside a Circle

Test every point against every circle with an exact integer distance check.

Approach

  1. For each query [xj, yj, rj], start a counter at 0.
  2. For each point, compute dx = x - xj, dy = y - yj and add one if dx² + dy² <= rj².
  3. Store the counter as answer[j].

Why it works

A point lies inside or on a circle exactly when its Euclidean distance to the centre is at most the radius; both sides are non-negative, so squaring preserves the comparison. Each point is checked once per query, so every count is exact, and duplicate points are counted as often as they appear.

Complexity

  • Time — O(n · q)
  • Space — O(q) for the answer

Pitfalls

  • Use <= — points on the boundary count.
  • Avoid sqrt; floating-point rounding can flip boundary points.
  • For the follow-up, sort points by x and only scan the strip [xj - rj, xj + rj], or bucket them on a grid.

Reference solution

Python

from typing import List

def countPoints(points: List[List[int]], queries: List[List[int]]) -> List[int]:
    answer = []
    for qx, qy, r in queries:
        rr = r * r
        c = 0
        for x, y in points:
            dx = x - qx
            dy = y - qy
            if dx * dx + dy * dy <= rr:
                c += 1
        answer.append(c)
    return answer

Java

public static int[] countPoints(int[][] points, int[][] queries) {
    int[] answer = new int[queries.length];
    for (int j = 0; j < queries.length; j++) {
        int qx = queries[j][0], qy = queries[j][1], rr = queries[j][2] * queries[j][2];
        int c = 0;
        for (int[] p : points) {
            int dx = p[0] - qx, dy = p[1] - qy;
            if (dx * dx + dy * dy <= rr) c++;
        }
        answer[j] = c;
    }
    return answer;
}

C++

vector<int> countPoints(vector<vector<int>>& points, vector<vector<int>>& queries) {
    vector<int> answer;
    for (auto& q : queries) {
        int rr = q[2] * q[2];
        int c = 0;
        for (auto& p : points) {
            int dx = p[0] - q[0], dy = p[1] - q[1];
            if (dx * dx + dy * dy <= rr) c++;
        }
        answer.push_back(c);
    }
    return answer;
}

JavaScript

var countPoints = function(points, queries) {
    var answer = [];
    for (var j = 0; j < queries.length; j++) {
        var qx = queries[j][0], qy = queries[j][1], rr = queries[j][2] * queries[j][2];
        var c = 0;
        for (var i = 0; i < points.length; i++) {
            var dx = points[i][0] - qx, dy = points[i][1] - qy;
            if (dx * dx + dy * dy <= rr) c++;
        }
        answer.push(c);
    }
    return answer;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays