{x}
blog image

Count Lattice Points Inside a Circle

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.

Note:

  • 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.

 

Example 1:

Input: circles = [[2,2,1]]
Output: 5
Explanation:
The figure above shows the given circle.
The lattice points present inside the circle are (1, 2), (2, 1), (2, 2), (2, 3), and (3, 2) and are shown in green.
Other points such as (1, 1) and (1, 3), which are shown in red, are not considered inside the circle.
Hence, the number of lattice points present inside at least one circle is 5.

Example 2:

Input: circles = [[2,2,2],[3,4,1]]
Output: 16
Explanation:
The figure above shows the given circles.
There are exactly 16 lattice points which are present inside at least one circle. 
Some of them are (0, 2), (2, 0), (2, 4), (3, 2), and (4, 4).

 

Constraints:

  • 1 <= circles.length <= 200
  • circles[i].length == 3
  • 1 <= xi, yi <= 100
  • 1 <= ri <= min(xi, yi)

Solution Explanation

This problem asks to count the number of lattice points (points with integer coordinates) that fall inside at least one circle in a given set of circles. Each circle is represented by its center coordinates (x, y) and radius r.

The most straightforward approach is brute force: iterate through all possible lattice points within a bounding box encompassing all circles and check if each point lies within any of the circles.

Algorithm

  1. Find Bounding Box: Determine the maximum x and y coordinates that could possibly contain a lattice point within any circle. This is done by finding the maximum x + r and y + r values across all circles. This forms our search space.

  2. Iterate through Lattice Points: Iterate through all integer coordinates (x, y) within the bounding box determined in step 1.

  3. Check Circle Containment: For each lattice point, iterate through all the circles. Check if the distance between the lattice point and the center of each circle is less than or equal to the circle's radius using the distance formula: sqrt((x - center_x)^2 + (y - center_y)^2). If the point is inside any circle, increment the counter.

  4. Return Count: After checking all lattice points, return the final count.

Time and Space Complexity Analysis

  • Time Complexity: O(N * M * K), where N is the number of circles, M is the maximum x-coordinate plus radius, and K is the maximum y-coordinate plus radius. The nested loops dominate the runtime.

  • Space Complexity: O(1). The algorithm uses only a constant amount of extra space to store variables.

Code Implementation (Python)

import math
 
class Solution:
    def countLatticePoints(self, circles: List[List[int]]) -> int:
        ans = 0
        mx = max(x + r for x, _, r in circles)
        my = max(y + r for _, y, r in circles)
        for i in range(mx + 1):
            for j in range(my + 1):
                for x, y, r in circles:
                    dist = math.sqrt((i - x)**2 + (j - y)**2)
                    if dist <= r:
                        ans += 1
                        break  # Point is in at least one circle, no need to check others
        return ans

The other language implementations (Java, C++, Go, TypeScript) follow the same logic, differing only in syntax and specific library functions. For example, the math.sqrt() function in Python would be Math.sqrt() in Java or std::sqrt() in C++. The core algorithmic approach remains consistent across all implementations.