Queries on Number of Points Inside a Circle

Medium

Asked by:

13 views

Topics:

Arrays

You are given an array points where points[i] = [x_i, y_i] is 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.

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 <= x_j, y_j <= 500
1 <= r_j <= 500
All coordinates are integers.

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected range for the coordinates of the points and the center of the circles, and the radius of the circles? Are they integers or floating-point numbers?
Can the input `points` array or the `circles` array be empty or null?
If a point lies exactly on the circumference of a circle, should it be considered inside the circle?
Are the circles guaranteed to be valid (i.e., will the radius always be non-negative)?
How should I handle potential integer overflow issues when calculating the distance between a point and a circle's center (specifically the square of the distance)?

Brute Force Solution

Approach

The brute force method for this problem involves checking each point against every circle individually. We see if each point falls within the boundaries of each circle and count the ones that do. Finally, we record these counts as the answer to the queries.

Here's how the algorithm would work step-by-step:

For each circle we're given, we need to figure out which points are inside it.
Take the first circle and look at the first point.
Calculate the distance between the center of the circle and the point.
If the calculated distance is less than or equal to the circle's radius, then the point is inside the circle, so count it.
Do the same thing for all other points with respect to the same circle to get the total number of points inside the first circle.
Store the count of points inside the first circle as the answer for the first query.
Repeat the process from step 2 for all the other circles.
Return all the stored counts - one for each circle - as the final answers.

Code Implementation

def count_points_inside_circles_brute_force(points, circles):
    results = []

    # Iterate through each circle
    for circle_index in range(len(circles)):
        circle_center_x = circles[circle_index][0]
        circle_center_y = circles[circle_index][1]
        circle_radius = circles[circle_index][2]
        points_inside_count = 0

        # Check each point against the current circle
        for point_index in range(len(points)):
            point_x = points[point_index][0]
            point_y = points[point_index][1]

            # Calculate the distance between point and circle center
            distance_x = point_x - circle_center_x
            distance_y = point_y - circle_center_y
            distance = (distance_x**2 + distance_y**2)**0.5

            # Check if the point is inside the circle
            if distance <= circle_radius:
                # Increment counter if point is within
                points_inside_count += 1

        # Store the result for the current circle
        results.append(points_inside_count)

    return results

Big(O) Analysis

Time Complexity

O(n*m) – The algorithm iterates through each circle in the queries array and, for each circle, it iterates through all the points in the points array. Let n be the number of points and m be the number of circles (queries). The distance calculation within the inner loop takes constant time. Therefore, the total number of operations is proportional to n multiplied by m, giving a time complexity of O(n*m).

Space Complexity

O(1) – The algorithm iterates through the points and circles. It only stores a count for each circle and calculates the distance between points and circle centers. No auxiliary data structures grow with the input size. Therefore, the space used is constant, independent of the number of points or circles.

Optimal Solution

Approach

We're trying to efficiently count how many points are inside each circle. The smart way to do this is to check each point against each circle one by one, but in an organized way that lets us avoid unnecessary calculations. We can reduce redundant calculations by checking only points inside a bounding square of the circle and using the distance formula.

Here's how the algorithm would work step-by-step:

For each circle, find a square that perfectly contains the entire circle.
Eliminate points outside of this square because these points can't be inside the circle.
For the remaining points (inside the square), calculate the distance between the point and the center of the circle.
If the distance is less than or equal to the circle's radius, then the point is inside the circle. Increase the counter for that circle.
Repeat the above steps for all circles, returning the count of points inside each circle.

Code Implementation

def count_points(points, queries):
    result = []
    for circle_index in range(len(queries)):
        circle_center_x, circle_center_y, circle_radius = queries[circle_index]
        point_count = 0

        # Define the bounds of the square containing the circle
        min_x = circle_center_x - circle_radius
        max_x = circle_center_x + circle_radius
        min_y = circle_center_y - circle_radius
        max_y = circle_center_y + circle_radius

        for point_index in range(len(points)):
            point_x, point_y = points[point_index]

            # Only check points within the bounding square
            if min_x <= point_x <= max_x and min_y <= point_y <= max_y:

                # Calculate distance between point and circle center
                distance = ((point_x - circle_center_x)**2 + (point_y - circle_center_y)**2)**0.5

                # Check if the point is inside the circle
                if distance <= circle_radius:
                    point_count += 1

        result.append(point_count)

    # Return the count of points inside each circle
    return result

Big(O) Analysis

Time Complexity

O(n*m) – Let n be the number of circles and m be the number of points. For each of the n circles, we iterate through all m points to check if they lie within the circle's bounding square. After the square bounding filter, in the worst case, we still compute the distance for each point inside the square. Therefore the total number of operations involves checking all m points for each of the n circles. This results in a time complexity of O(n*m).

Space Complexity

O(1) – The algorithm iterates through the circles and points, but the primary extra memory usage comes from a counter for each circle. This counter stores the number of points inside each circle. Since the number of these counters is determined by the number of circles, the space remains constant with respect to the number of points. Furthermore, only a few scalar variables are used for distance calculations and boolean checks, and the space they occupy is constant, regardless of the number of circles or points. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty points array	Return an empty list of counts immediately as there are no points to check against any circles.
Empty queries array	Return an empty list of counts immediately as there are no circles to query.
Points with very large or very small coordinates (potential overflow)	Use long data type for distance calculation to prevent integer overflow, or use appropriate libraries to deal with arbitrary sized numbers.
Queries with very large or very small radius (potential overflow)	Use long data type for distance calculation to prevent integer overflow, or use appropriate libraries to deal with arbitrary sized numbers.
Points clustered far away from any circles	The solution correctly handles this by returning zero for each query as no points are inside the circles.
Points concentrated near the circle's boundary; floating point precision issues	Implement a small tolerance value (epsilon) when comparing the distance to the radius to account for floating-point precision errors.
Large number of points and queries; performance concerns	Optimize by considering spatial partitioning techniques (e.g., KD-trees) if the naive O(m*n) complexity is too slow.
Points with coordinates of zero	The distance calculation handles zero coordinates correctly by not causing divide by zero or other mathematical exceptions.

Empty points array

How to Handle:

Return an empty list of counts immediately as there are no points to check against any circles.

Empty queries array

How to Handle:

Return an empty list of counts immediately as there are no circles to query.

Points with very large or very small coordinates (potential overflow)

How to Handle:

Use long data type for distance calculation to prevent integer overflow, or use appropriate libraries to deal with arbitrary sized numbers.

Queries with very large or very small radius (potential overflow)

How to Handle:

Use long data type for distance calculation to prevent integer overflow, or use appropriate libraries to deal with arbitrary sized numbers.

Points clustered far away from any circles

How to Handle:

The solution correctly handles this by returning zero for each query as no points are inside the circles.

Points concentrated near the circle's boundary; floating point precision issues

How to Handle:

Implement a small tolerance value (epsilon) when comparing the distance to the radius to account for floating-point precision errors.

Large number of points and queries; performance concerns

How to Handle:

Optimize by considering spatial partitioning techniques (e.g., KD-trees) if the naive O(m*n) complexity is too slow.

Points with coordinates of zero

How to Handle:

The distance calculation handles zero coordinates correctly by not causing divide by zero or other mathematical exceptions.