Leetcode 2249: Count Lattice Points Inside a Circle

Input: The input consists of a list of circles, where each circle is defined by its center coordinates and radius.

Example: circles = [[3, 4, 2], [6, 7, 1]]

Constraints:

• 1 <= circles.length <= 200

• circles[i].length == 3

• 1 <= xi, yi <= 100

• 1 <= ri <= min(xi, yi)

Output: Return an integer representing the number of distinct lattice points inside at least one circle.

Example: Output: 14

Constraints:

Goal: Count the distinct lattice points that are inside or on the circumference of at least one of the given circles.

Steps:

• Iterate through each circle in the input.

• For each circle, iterate through all points in the bounding square defined by the circle's radius.

• Check whether each point lies inside or on the circle using the distance formula.

• Use a data structure like a set to keep track of unique lattice points.

Goal: Ensure that all operations respect the bounds of the input size and circle radius.

Steps:

• Number of circles does not exceed 200.

• All coordinates and radius values are within the specified range.

Assumptions:

• Circle centers and radii are positive integers.

• The grid is large enough to accommodate all specified circles.

• Input: circles = [[3, 3, 2]]

• Explanation: The circle with center (3, 3) and radius 2 includes lattice points (1, 3), (2, 2), (2, 3), (2, 4), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (4, 2), (4, 3), (4, 4), (5, 3). The total count is 13.

• Input: circles = [[2, 2, 1], [4, 4, 1]]

• Explanation: The circles include lattice points (1, 2), (2, 1), (2, 2), (2, 3), (3, 2), (3, 4), (4, 3), (4, 4), (4, 5), (5, 4). After merging overlapping points, the total count is 10.

Approach: Use brute-force bounding box iteration for each circle and a set to ensure unique points.

Observations:

• A lattice point inside or on a circle satisfies the equation (x - xi)^2 + (y - yi)^2 <= ri^2.

• Overlap between circles requires merging results to avoid duplicate counts.

• Using a set data structure ensures that duplicate lattice points are not counted multiple times.

Steps:

• Iterate over each circle and determine its bounding box as [xi - ri, xi + ri] x [yi - ri, yi + ri].

• Check each point in the bounding box to see if it lies inside or on the circle using the circle equation.

• Store each valid point in a set.

• Return the size of the set as the final result.

Empty Inputs:

• No circles are provided; return 0.

Large Inputs:

• Handle up to 200 circles with maximum radius efficiently.

Special Values:

• Circles with a radius of 1 will include only the center and nearby lattice points.

Constraints:

• Bounding box iteration should remain within computational limits for given constraints.

int countLatticePoints(vector<vector<int>>& cir) {
    set<int> cnt;
    
    for(auto it: cir) {
        
        for(int i = it[0] - it[2]; i <= it[0] + it[2]; i++)
        for(int j = it[1] - it[2]; j <= it[1] + it[2]; j++)                
            if((i - it[0]) * (i - it[0]) + (j - it[1]) * (j - it[1]) <= (it[2] * it[2]))
                cnt.insert(i * 1000 + j);
        
    }
    return cnt.size();
}

1 : Function Definition

int countLatticePoints(vector<vector<int>>& cir) {

This is the start of the 'countLatticePoints' function, which takes a vector of circles (defined by their center coordinates and radius) and calculates the number of unique lattice points contained within these circles.

2 : Variable Initialization

    set<int> cnt;

A set 'cnt' is declared to store unique lattice points. The set ensures that duplicate points are automatically handled.

3 : Loop Through Circles

    for(auto it: cir) {

This loop iterates over each circle in the 'cir' vector. Each circle is represented by a vector with its center (x, y) and radius.

4 : Loop Through x-coordinates

        for(int i = it[0] - it[2]; i <= it[0] + it[2]; i++)

This loop iterates over the x-coordinates that might lie within the circle, considering the range from the leftmost to the rightmost points based on the center's x-coordinate and radius.

5 : Loop Through y-coordinates

        for(int j = it[1] - it[2]; j <= it[1] + it[2]; j++)

This loop iterates over the y-coordinates that might lie within the circle, considering the range from the bottommost to the topmost points based on the center's y-coordinate and radius.

6 : Point Inside Circle Check

            if((i - it[0]) * (i - it[0]) + (j - it[1]) * (j - it[1]) <= (it[2] * it[2]))

This line checks whether the point (i, j) lies inside the circle. The condition is derived from the equation of a circle, where the sum of the squares of the differences in coordinates must be less than or equal to the square of the radius.

7 : Insert Point

                cnt.insert(i * 1000 + j);

If the point (i, j) lies inside the circle, it is inserted into the 'cnt' set. The points are stored as a unique identifier by combining the x and y coordinates.

8 : Return Unique Count

    return cnt.size();

Returns the size of the set 'cnt', which represents the number of unique lattice points that lie within the given circles.

Best Case: O(n * r^2)

Average Case: O(n * r^2)

Worst Case: O(n * r^2)

Description: Each circle's bounding box involves iterating over r^2 points, where n is the number of circles.

Best Case: O(m)

Worst Case: O(m)

Description: The space complexity is determined by the number of unique lattice points m.

Leetcode 2249: Count Lattice Points Inside a Circle

Explore →