# Count Lattice Points Inside a Circle
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-lattice-points-inside-a-circle)
Canonical: https://scaleengineer.com/dsa/problems/count-lattice-points-inside-a-circle
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Geometry](https://scaleengineer.com/dsa/patterns/geometry), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** Array, Hash Table
**Companies:** [Rubrik](https://scaleengineer.com/companies/rubrik)
---
## Problem
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:**

![](https://assets.glich.co/dsa/count-lattice-points-inside-a-circle/image0.png) 

**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:**

![](https://assets.glich.co/dsa/count-lattice-points-inside-a-circle/image1.png) 

**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)`

# Approaches
## Brute-Force Grid Scan
This approach involves iterating through every possible lattice point within a large bounding box that is guaranteed to encompass all circles. For each point, we check if it lies inside any of the given circles.
**Time:** O(MaxX * MaxY * N), where N is the number of circles, and MaxX, MaxY are the dimensions of the grid (approx. 201x201). Given the constraints, this is roughly `201 * 201 * 200`, which is feasible but slow. · **Space:** O(K), where K is the number of unique lattice points found. In the worst case, this can be up to O(MaxX * MaxY), which is O(201*201) given the constraints.
**Pros:** Simple to understand and implement.
**Cons:** Highly inefficient because it iterates over every point in a large 201x201 grid, even if points are far away from any circle.
### Explanation
First, we determine the maximum possible coordinate values based on the problem constraints. Since `x_i, y_i <= 100` and `r_i <= 100`, the maximum coordinate a circle can reach is `100 + 100 = 200`. The minimum coordinate is non-negative because `r_i <= min(x_i, y_i)`. Thus, we can define a search grid from `(0, 0)` to `(200, 200)`.

We use a `HashSet<String>` to store the unique lattice points that are found inside at least one circle. This prevents duplicate counting. The algorithm proceeds by iterating through each point `(px, py)` in this grid. For each point, it then checks against every circle. If the point is found to be inside any circle, it's added to the set, and we can stop checking other circles for this specific point and move to the next point in the grid.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int countLatticePoints(int[][] circles) {
        Set<String> points = new HashSet<>();
        // Based on constraints, max coordinate is 100+100=200.
        // The grid to check is from (0,0) to (200,200).
        for (int px = 0; px <= 200; px++) {
            for (int py = 0; py <= 200; py++) {
                for (int[] c : circles) {
                    int x = c[0], y = c[1], r = c[2];
                    // Check if point (px, py) is inside the circle
                    if ((px - x) * (px - x) + (py - y) * (py - y) <= r * r) {
                        points.add(px + "," + py);
                        break; // Found in one circle, no need to check others for this point
                    }
                }
            }
        }
        return points.size();
    }
}
```
### Algorithm
- Initialize a `HashSet` to store the unique lattice points found.
- Determine the overall bounding box for all circles. Based on constraints (`x, y <= 100`, `r <= 100`), a grid from `(0,0)` to `(200,200)` is sufficient.
- Iterate through every x-coordinate `px` from 0 to 200.
- Inside this loop, iterate through every y-coordinate `py` from 0 to 200.
- For each lattice point `(px, py)`, iterate through all the circles `(x_i, y_i, r_i)`.
- Check if the point is inside the current circle using the distance formula: `(px - x_i)^2 + (py - y_i)^2 <= r_i^2`.
- If the condition is true, add the point to the `HashSet` and break the inner loop (over circles) to proceed to the next lattice point.
- The final answer is the size of the `HashSet`.

## Iterating Through Circles' Bounding Boxes
A more optimized approach is to iterate through each circle individually. For each circle, we only need to check the lattice points within its own bounding box, which is a much smaller area than the entire grid. This avoids checking vast empty spaces.
**Time:** O(N * R_max^2), where N is the number of circles and R_max is the maximum possible radius (100). We iterate through N circles, and for each, we check a square grid of side length `2*r + 1`. This is significantly faster than the first approach. · **Space:** O(K), where K is the number of unique lattice points. In the worst case, this is bounded by the area of the grid, O(MaxX * MaxY).
**Pros:** Much more efficient than the full grid scan, as it limits the search space for each circle.; Handles overlapping circles correctly and automatically via the HashSet.
**Cons:** Using a `HashSet` of strings incurs overhead from string creation, concatenation, and hashing for each point added.
### Explanation
Instead of a single large loop over the entire grid, we loop through the circles first. This is more efficient because the search space for points is constrained for each circle.

We initialize a `HashSet` to store the unique lattice points, which handles duplicates from overlapping circles automatically. We iterate through each circle `(x, y, r)`. For each one, we define its bounding box: x-coordinates from `x - r` to `x + r`, and y-coordinates from `y - r` to `y + r`. We then loop through every lattice point `(px, py)` within this box. For each point, we apply the distance formula `(px - x)^2 + (py - y)^2 <= r^2` to confirm it's truly inside the circle. If it is, we add it to our `HashSet`.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int countLatticePoints(int[][] circles) {
        Set<String> points = new HashSet<>();
        for (int[] c : circles) {
            int x = c[0], y = c[1], r = c[2];
            // Iterate over the bounding box of the circle
            for (int px = x - r; px <= x + r; px++) {
                for (int py = y - r; py <= y + r; py++) {
                    // Check if the point (px, py) is inside the circle
                    if ((px - x) * (px - x) + (py - y) * (py - y) <= r * r) {
                        points.add(px + "," + py);
                    }
                }
            }
        }
        return points.size();
    }
}
```
### Algorithm
- Initialize an empty `HashSet` called `points` to store unique lattice points.
- Iterate through each circle `c` with center `(x, y)` and radius `r` in the `circles` array.
- For the current circle, iterate through all x-coordinates `px` from `x - r` to `x + r`.
- For each `px`, iterate through all y-coordinates `py` from `y - r` to `y + r`.
- This defines the bounding box of the circle.
- Check if the point `(px, py)` is actually inside the circle using the condition `(px - x)^2 + (py - y)^2 <= r^2`.
- If it is, add a string representation of the point (e.g., `"px,py"`) to the `points` set.
- Return the final size of the `points` set.

## Optimized Scan with a 2D Boolean Grid
This approach builds upon the circle-by-circle scan by replacing the `HashSet` with a 2D boolean array. This is often more performant in a constrained environment like this problem, as it avoids the overhead of string operations and hashing by using direct array access to mark visited points.
**Time:** O(N * R_max^2). The asymptotic time complexity is identical to the `HashSet` version, but the constant factors are smaller, making it faster in practice. · **Space:** O(MaxX * MaxY). We allocate a fixed-size grid of `201 * 201`. This is constant space because it depends on the problem's constraints, not the size of the input `circles` array.
**Pros:** Most efficient in practice due to direct array access, which avoids string manipulation and hashing overhead.; Space complexity is constant with respect to the problem's coordinate constraints.
**Cons:** Space complexity is fixed and large, determined by the grid constraints, not the input size. It might be wasteful if the covered points are very few and sparse.
### Explanation
The core logic remains the same: iterate through each circle and check the points in its bounding box. However, instead of a `HashSet`, we declare a 2D boolean array, `grid[201][201]`, to represent the lattice. We also initialize an integer counter `count` to 0.

As we iterate through the points `(px, py)` in each circle's bounding box, we first check if the point is inside the circle. If it is, we then check `grid[px][py]`. If it's `false`, it means we haven't counted this point yet. We then set `grid[px][py]` to `true` and increment our `count`. If `grid[px][py]` is already `true`, we do nothing, as the point has already been counted from a previous circle.

```java
class Solution {
    public int countLatticePoints(int[][] circles) {
        boolean[][] grid = new boolean[201][201];
        int count = 0;
        for (int[] c : circles) {
            int x = c[0], y = c[1], r = c[2];
            // Iterate over the bounding box of the circle
            for (int px = x - r; px <= x + r; px++) {
                for (int py = y - r; py <= y + r; py++) {
                    // Check if the point (px, py) is inside the circle
                    if ((px - x) * (px - x) + (py - y) * (py - y) <= r * r) {
                        if (!grid[px][py]) {
                            grid[px][py] = true;
                            count++;
                        }
                    }
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a 2D boolean array `grid[201][201]` to all `false`.
- Initialize a counter `count` to 0.
- Iterate through each circle `c` with center `(x, y)` and radius `r`.
- For the current circle, iterate through x-coordinates `px` from `x - r` to `x + r`.
- For each `px`, iterate through y-coordinates `py` from `y - r` to `y + r`.
- Check if `(px - x)^2 + (py - y)^2 <= r^2`.
- If the condition is true and `grid[px][py]` is `false`:
  - Set `grid[px][py]` to `true`.
  - Increment `count`.
- Return the final `count`.

# Solutions
### Java

```java
class Solution {
public
  int countLatticePoints(int[][] circles) {
    int mx = 0, my = 0;
    for (var c : circles) {
      mx = Math.max(mx, c[0] + c[2]);
      my = Math.max(my, c[1] + c[2]);
    }
    int ans = 0;
    for (int i = 0; i <= mx; ++i) {
      for (int j = 0; j <= my; ++j) {
        for (var c : circles) {
          int dx = i - c[0], dy = j - c[1];
          if (dx * dx + dy * dy <= c[2] * c[2]) {
            ++ans;
            break;
          }
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int countLatticePoints(vector<vector<int>> &circles) {
    int mx = 0, my = 0;
    for (auto &c : circles) {
      mx = max(mx, c[0] + c[2]);
      my = max(my, c[1] + c[2]);
    }
    int ans = 0;
    for (int i = 0; i <= mx; ++i) {
      for (int j = 0; j <= my; ++j) {
        for (auto &c : circles) {
          int dx = i - c[0], dy = j - c[1];
          if (dx * dx + dy * dy <= c[2] * c[2]) {
            ++ans;
            break;
          }
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
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: dx, dy = i - x, j - y if dx * dx + dy * dy <= r * r: ans += 1 break return ans

```