Watch 8 video solutions for Count Lattice Points Inside a Circle, a medium level problem involving Array, Hash Table, Math. This walkthrough by Coding Decoded has 2,101 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |