LeetCode 2249: Count Lattice Points Inside a Circle

Explanation

To solve this problem, we can iterate through each lattice point on the grid and check if it lies inside at least one circle. To determine if a lattice point is inside a circle, we calculate the distance between the lattice point and the center of each circle. If the distance is less than or equal to the radius of the circle, the lattice point is considered inside the circle.

1. Iterate through each lattice point on the grid.
2. For each lattice point, iterate through each circle and calculate the distance between the lattice point and the center of the circle.
3. If the distance is less than or equal to the radius of the circle, increment the count of lattice points inside at least one circle.
4. Return the total count of lattice points inside circles.

Time complexity: O(n * m) where n is the number of lattice points and m is the number of circles.
Space complexity: O(1)

class Solution {
    public int countLatticePoints(int[][] circles) {
        int count = 0;
        
        for (int x = 1; x <= 100; x++) {
            for (int y = 1; y <= 100; y++) {
                boolean insideCircle = false;
                for (int[] circle : circles) {
                    int cx = circle[0];
                    int cy = circle[1];
                    int r = circle[2];
                    
                    if ((x - cx) * (x - cx) + (y - cy) * (y - cy) <= r * r) {
                        insideCircle = true;
                        break;
                    }
                }
                if (insideCircle) {
                    count++;
                }
            }
        }
        
        return count;
    }
}