Queries on Number of Points Inside a Circle

Queries on Number of Points Inside a Circle - Problem

You are given an array points where points[i] = [x_i, y_i] represents the coordinates of the i-th point on a 2D plane. Multiple points can have the same coordinates.

You are also given an array queries where queries[j] = [x_j, y_j, r_j] describes a circle centered at (x_j, y_j) with a radius of r_j.

For each query queries[j], compute the number of points inside the j-th circle. Points on the border of the circle are considered inside.

Return an array answer, where answer[j] is the answer to the j-th query.

Input & Output

Example 1 — Basic Case

$ Input: points = [[1,3],[3,3],[5,3],[2,2]], queries = [[2,3,1],[4,3,1]]

› Output: [3,2]

💡 Note: For query [2,3,1]: Points [1,3], [3,3], [2,2] are within distance 1 of center (2,3). For query [4,3,1]: Points [3,3], [5,3] are within distance 1 of center (4,3).

Example 2 — Points on Border

$ Input: points = [[1,1],[2,2],[3,3]], queries = [[1,1,1]]

› Output: [2]

💡 Note: Point [1,1] is at center (distance 0), point [2,2] is at distance √2 ≈ 1.41 > 1, point [3,3] is at distance √8 ≈ 2.83 > 1. Only [1,1] and points exactly at distance 1 would count.

Example 3 — Large Radius

$ Input: points = [[1,1],[2,2],[3,3]], queries = [[2,2,2]]

› Output: [3]

💡 Note: All points [1,1], [2,2], [3,3] are within distance 2 of center (2,2). Distances are √2, 0, √2 respectively, all ≤ 2.

Constraints

1 ≤ points.length ≤ 500
points[i].length == 2
1 ≤ queries.length ≤ 500
queries[j].length == 3
0 ≤ x_i, y_i, x_j, y_j ≤ 500
1 ≤ r_j ≤ 500

Visualization

Tap to expand

Understanding the Visualization

Input

Points scattered on 2D plane and circle queries

Process

Calculate distance from each point to each circle center

Output

Count of points inside each circle

Key Takeaway

🎯 Key Insight: Use squared distance comparison to avoid expensive square root calculations while maintaining accuracy

Asked in

G Google 25 M Microsoft 18 a Amazon 15

The key insight is to use the distance formula to determine if each point lies within each circle's radius. The best approach uses squared distance comparison to avoid expensive square root calculations and floating-point precision issues. Time: O(n×m), Space: O(1) where n is number of points and m is number of queries.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n × m)	O(1)	For each query, check all points to see if they're inside the circle
Optimized with Squared Distance	O(n × m)	O(1)	Avoid expensive square root calculations by comparing squared distances

Brute Force — Algorithm Steps

For each query circle
Check every point against this circle
Calculate distance using formula: sqrt((x1-x2)² + (y1-y2)²)
Count points where distance ≤ radius

Visualization

Tap to expand

Step-by-Step Walkthrough

Query 1

Check all points against first circle

Query 2

Check all points against second circle

Result

Count of points inside each circle

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int** points, int pointsSize, int** queries, int queriesSize, int* returnSize) {
    int* result = (int*)malloc(queriesSize * sizeof(int));
    *returnSize = queriesSize;
    
    for (int i = 0; i < queriesSize; i++) {
        int cx = queries[i][0];
        int cy = queries[i][1];
        int r = queries[i][2];
        int count = 0;
        
        for (int j = 0; j < pointsSize; j++) {
            int px = points[j][0];
            int py = points[j][1];
            // Calculate squared distance to avoid floating point precision issues
            long long distSquared = (long long)(px - cx) * (px - cx) + (long long)(py - cy) * (py - cy);
            if (distSquared <= (long long)r * r) {
                count++;
            }
        }
        
        result[i] = count;
    }
    
    return result;
}

int main() {
    // Simplified parsing for demo - in practice would need proper JSON parsing
    int pointsSize = 3;
    int** points = (int**)malloc(pointsSize * sizeof(int*));
    for (int i = 0; i < pointsSize; i++) {
        points[i] = (int*)malloc(2 * sizeof(int));
    }
    points[0][0] = 1; points[0][1] = 3;
    points[1][0] = 3; points[1][1] = 3;
    points[2][0] = 5; points[2][1] = 3;
    
    int queriesSize = 2;
    int** queries = (int**)malloc(queriesSize * sizeof(int*));
    for (int i = 0; i < queriesSize; i++) {
        queries[i] = (int*)malloc(3 * sizeof(int));
    }
    queries[0][0] = 2; queries[0][1] = 3; queries[0][2] = 1;
    queries[1][0] = 4; queries[1][1] = 3; queries[1][2] = 1;
    
    int returnSize;
    int* result = solution(points, pointsSize, queries, queriesSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m)

For each of m queries, we check all n points

✓ Linear Growth

Space Complexity

O(1)

Only using variables for calculations, no extra data structures

✓ Linear Space

23.4K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler