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:
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 <= 200circles[i].length == 31 <= xi, yi <= 1001 <= ri <= min(xi, yi)Problem Overview: You are given multiple circles on a 2D grid where each circle is defined by (x, y, r). The task is to count how many integer lattice points lie inside at least one circle. A lattice point (i, j) is inside a circle if (i - x)^2 + (j - y)^2 ≤ r^2.
Approach 1: Brute Force with Bounding Box (Time: O(n · r²), Space: O(k))
Each circle defines a square bounding box from x - r to x + r and y - r to y + r. Iterate through every integer coordinate inside this box and check the circle equation (dx * dx + dy * dy ≤ r²). If the point lies inside the circle, store it in a hash set to avoid counting duplicates from overlapping circles. This method relies on simple geometry and grid enumeration. The approach is straightforward to implement and works well because the radius is relatively small, but it still scans many unnecessary points in the bounding square.
Approach 2: Efficient Bounded Search with Optimization (Time: O(n · r²), Space: O(k))
This version still limits exploration to each circle's bounding square but reduces redundant checks by focusing only on coordinates that could realistically satisfy the circle equation. For every x in the horizontal range [cx - r, cx + r], compute the maximum vertical distance allowed by rearranging the equation: dy ≤ sqrt(r² - dx²). Then enumerate only the valid y values within that vertical span. Each discovered lattice point is inserted into a set (using a hash table) so overlapping circles do not double count points. This cuts many unnecessary distance checks and performs well even when circles overlap heavily.
Recommended for interviews: Start with the bounding-box brute force to demonstrate the geometric condition and enumeration logic. Interviewers usually expect the optimized bounded search afterward. The optimization shows that you can manipulate the circle equation and reduce the search area while still guaranteeing correctness.
This approach entails examining each point within the bounding box of each circle. For every point, we check whether it lies inside the circle using the equation of a circle.
The brute force solution may not be optimal but it's straightforward and ensures that we capture all lattice points within the circles.
The C solution uses a set to store unique lattice points. For each circle, it evaluates each potential lattice point within the bounding box around the circle, checking whether the point lies within the circle. The calculation is optimized with dx and dy.
Time Complexity: O(n * r^2), where n is the number of circles and r is the average radius of the circles.
Space Complexity: O(n * r^2), due to the storage of lattice points.
In this approach, we exploit the properties of circles and symmetry for optimization. We limit the lattice point evaluation to only one quadrant and reflect results to others, reducing computation time.
This C solution optimizes by evaluating lattice points in only a single quadrant, leveraging symmetry to reflect results. The solution calculates dy using the circle's equation, adding centered reflected points to a set.
Time Complexity: O(n * r)
Space Complexity: O(n * r^2)
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Brute Force with Bounding Box | Time Complexity: O(n * r^2), where n is the number of circles and r is the average radius of the circles. |
| Efficient Bounded Search with Optimization | Time Complexity: O(n * r) |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Bounding Box | O(n · r²) | O(k) | Good starting approach. Simple geometry check for every grid point in the bounding square. |
| Efficient Bounded Search with Optimization | O(n · r²) | O(k) | Preferred solution. Reduces unnecessary checks by computing valid vertical ranges using the circle equation. |
Count Lattice Points Inside a Circle | Leetcode 2249 | Maths | Contest 290 🔥🔥 • Coding Decoded • 2,101 views views
Watch 7 more video solutions →Practice Count Lattice Points Inside a Circle with our built-in code editor and test cases.
Practice on FleetCode