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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Lattice Points Inside a Circle

Difficulty: Medium

Problem Description

Given a 2D integer array circles where circles[i] = [xi, yi, ri] represents the center (xi, yi) and radius ri of the ith circle drawn on a grid, return the number of lattice points that are present inside at least one circle. A lattice point is a point with integer coordinates. Points that lie on the circumference of a circle are also considered to be inside it.

Key Insights

  • A lattice point is defined as a point with integer coordinates.
  • The distance from the center of a circle to a lattice point can be calculated using the Euclidean distance formula.
  • A lattice point (x, y) is inside or on the circle if (x - xi)² + (y - yi)² ≤ ri².
  • The maximum radius and center coordinates allow us to limit the range of points we need to check.
  • Using a set data structure can help avoid counting duplicate lattice points.

Space and Time Complexity

Time Complexity: O(n * r²), where n is the number of circles and r is the maximum radius of the circles.
Space Complexity: O(m), where m is the number of unique lattice points stored in the set.

Solution

To solve this problem, we will iterate through each circle, calculate the potential lattice points that could lie within the circle, and store them in a set to ensure uniqueness. For each circle defined by its center (xi, yi) and radius ri, we will check all integer coordinates (x, y) such that (x - xi)² + (y - yi)² ≤ ri². By iterating over the ranges of x and y based on the radius, we can efficiently identify all relevant lattice points.

Code Solutions

def countLatticePoints(circles):
    points = set()  # To store unique lattice points
    for x, y, r in circles:
        # Iterate over the square bounding box of the circle
        for dx in range(-r, r + 1):
            for dy in range(-r, r + 1):
                if dx * dx + dy * dy <= r * r:  # Check if within circle
                    points.add((x + dx, y + dy))  # Add unique point
    return len(points)  # Return the number of unique points

# Example usage
print(countLatticePoints([[2, 2, 1]]))  # Output: 5
← Back to All Questions