We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Queries on Number of Points Inside a Circle

Number: 1939

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

You are given a list of points in a 2D plane and an array of queries where each query describes a circle (with a center point and a radius). For each query, count how many points fall inside or on the boundary of the circle.

Key Insights

  • Use the distance formula (squared) to compare the distance between a point and the query center without using square roots.
  • Check if (point_x - query_x)² + (point_y - query_y)² is less than or equal to radius².
  • The constraints (with points and queries up to 500 each) allow a simple O(n * m) solution.
  • For the follow-up aiming for better than O(n) per query, consider spatial indexing (such as a k-d tree or sorting followed by binary search), though the naive solution is acceptable given the constraint sizes.

Space and Time Complexity

Time Complexity: O(n * m) where n is the number of points and m is the number of queries. Space Complexity: O(1) extra space (ignoring input and output data storage).

Solution

For each query, iterate over all points and calculate the squared distance between the point and the center of the circle. If this squared distance is less than or equal to the squared radius, the point is inside the circle (or on its boundary). Increment the count for that query accordingly and return the results for all queries.

Code Solutions

# Python solution with line-by-line comments

def countPoints(points, queries):
    # Initialize the list to store counts for each query
    result = []
    # Loop over each query: center_x, center_y, radius
    for (qx, qy, r) in queries:
        count = 0
        # Precompute r^2 to compare with squared distances
        r_squared = r * r
        # Check each point in points list
        for (px, py) in points:
            # Calculate squared distance from point (px, py) to query center (qx, qy)
            if (px - qx) * (px - qx) + (py - qy) * (py - qy) <= r_squared:
                count += 1
        # Append the count for this query to result list
        result.append(count)
    return result

# Example usage:
points = [[1,3],[3,3],[5,3],[2,2]]
queries = [[2,3,1],[4,3,1],[1,1,2]]
print(countPoints(points, queries))  # Expected output: [3, 2, 2]
← Back to All Questions