Count Lattice Points Inside a Circle - Solution & Explanation
Problem Statement
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 <= 200circles[i].length == 31 <= xi, yi <= 1001 <= ri <= min(xi, yi)
Approach Overview
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 1: Brute Force with Bounding Box
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.
Complexity
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.
Approach 2: Efficient Bounded Search with Optimization
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.
Complexity
Time Complexity: O(n * r)
Space Complexity: O(n * r^2)
Approach 3: Default Approach
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Count Lattice Points Inside a Circle | Leetcode 2249 | Maths | Contest 290 🔥🔥 • Coding Decoded • 2,139 views views
Watch 7 more video solutions →Frequently Asked Questions
Is Count Lattice Points Inside a Circle easy or hard?
Count Lattice Points Inside a Circle Python/Java solution
How to solve Count Lattice Points Inside a Circle in O(n · r²)?
What is the best approach for Count Lattice Points Inside a Circle?
Is Count Lattice Points Inside a Circle asked at Google/Amazon/Meta?
What data structure is used in Count Lattice Points Inside a Circle?
What is the time complexity of Count Lattice Points Inside a Circle?
Ready to solve this problem?
Practice Count Lattice Points Inside a Circle with our built-in code editor and test cases.
Practice on FleetCode