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

Count Lattice Points Inside a Circle

Number: 2332

Difficulty: Medium

Paid? No

Companies: Rubrik

Problem Description

Given an array of circles where each circle is represented by its center (x, y) and radius r, count the number of unique lattice points (points with integer coordinates) that are inside at least one circle. A point on the circle’s circumference is considered inside it.

Key Insights

  • Each circle defines a bounded region: from (x - r) to (x + r) in the x-direction and (y - r) to (y + r) in the y-direction.
  • For any potential lattice point within these bounds, check if it satisfies (point_x - circle_x)² + (point_y - circle_y)² <= r².
  • Use a set (or similar data structure) to avoid counting duplicate lattice points that lie within multiple circles.
  • The problem can be solved via simple enumeration because the maximum search area is small enough given the constraints.

Space and Time Complexity

Time Complexity: O(n * r^2) per circle. In worst-case, each circle might cover O(r^2) lattice points with n circles, hence overall iterations could be around O(n * (2r+1)^2). Space Complexity: O(n * r^2) in the worst-case due to the storage of lattice points in a set.

Solution

The solution iterates through each circle and considers all lattice points within the bounding box defined by the circle. For each lattice point, it checks whether the point lies inside or on the circumference using the equation (x - center_x)² + (y - center_y)² <= r². A set is utilized to ensure that each lattice point is counted once even if it belongs to multiple circles.

Code Solutions

# Define a function that counts lattice points inside at least one circle.
def countLatticePoints(circles):
    # A set to store unique lattice points
    lattice_points = set()
    
    # Loop over each circle defined by center (x, y) and radius r
    for (x_center, y_center, radius) in circles:
        # Compute the boundaries for x and y based on the circle's radius
        for x in range(x_center - radius, x_center + radius + 1):
            for y in range(y_center - radius, y_center + radius + 1):
                # Check if the point (x, y) is inside or on the circle
                if (x - x_center) ** 2 + (y - y_center) ** 2 <= radius ** 2:
                    lattice_points.add((x, y))
    
    # Return the total count of unique lattice points
    return len(lattice_points)

# Example usage:
circles = [[2, 2, 2], [3, 4, 1]]
print(countLatticePoints(circles))  # Expected output: 16
← Back to All Questions