# LeetCode 1020: Number of Enclaves

## Problem Restatement

We are given a binary matrix `grid` where `0` represents sea and `1` represents land.

A move consists of walking from one land cell to an adjacent (4-directional) land cell.

We need to return the number of land cells from which it is **impossible** to walk off the boundary of the grid.

Land cells connected to the boundary are not counted.

The official constraints state that `m == grid.length`, `n == grid[i].length`, `1 <= m, n <= 500`, and `grid[i][j]` is either `0` or `1`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Binary matrix `grid` |
| Output | Number of inland land cells with no path to the boundary |

Function shape:

```python
def numEnclaves(grid: list[list[int]]) -> int:
    ...
```

## Examples

Example 1:

```python
grid = [
    [0, 0, 0, 0],
    [1, 0, 1, 0],
    [0, 1, 1, 0],
    [0, 0, 0, 0],
]
```

The land cell at `(1, 0)` is on the left boundary and can walk off.

The cells at `(1, 2)`, `(2, 1)`, `(2, 2)` form an interior cluster with no boundary connection.

Answer:

```python
3
```

Example 2:

```python
grid = [
    [0, 1, 1, 0],
    [0, 0, 1, 0],
    [0, 0, 1, 0],
    [0, 0, 0, 0],
]
```

All land cells are connected to the top boundary.

Answer:

```python
0
```

## Key Insight

Any land cell connected (directly or indirectly) to a boundary land cell can reach the boundary.

So we find all land cells reachable from the boundary using BFS or DFS. The remaining land cells are enclaves.

## Algorithm

1. Add all boundary land cells to a queue.
2. BFS: mark all reachable land cells.
3. Count remaining land cells that are not marked.

## Correctness

BFS from boundary land cells visits exactly the land cells that are connected to the boundary.

All remaining land cells form enclaves because they have no path to the boundary.

## Edge Cases

- Mark nodes or cells as visited at enqueue/discovery time to avoid duplicate work.
- Return the failure value when the destination is unreachable.
- Check grid or graph boundaries before reading neighbors.

## Complexity

Let `m` and `n` be the grid dimensions.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(m * n)` | Each cell is visited at most once |
| Space | `O(m * n)` | Queue and visited set |

## Common Pitfalls

- Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
- Prefer problem-specific names over one-letter variables once the logic becomes stateful.

## Implementation

```python
from collections import deque

class Solution:
    def numEnclaves(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
        visited = [[False] * n for _ in range(m)]
        queue = deque()

        for r in range(m):
            for c in range(n):
                if (r == 0 or r == m - 1 or c == 0 or c == n - 1) and grid[r][c] == 1:
                    queue.append((r, c))
                    visited[r][c] = True

        while queue:
            r, c = queue.popleft()
            for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n and not visited[nr][nc] and grid[nr][nc] == 1:
                    visited[nr][nc] = True
                    queue.append((nr, nc))

        return sum(
            grid[r][c] == 1 and not visited[r][c]
            for r in range(m)
            for c in range(n)
        )
```

## Code Explanation

Initialize BFS from all boundary land cells:

```python
if (r == 0 or r == m - 1 or c == 0 or c == n - 1) and grid[r][c] == 1:
    queue.append((r, c))
    visited[r][c] = True
```

Expand BFS to all reachable land cells:

```python
while queue:
    r, c = queue.popleft()
    for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        nr, nc = r + dr, c + dc
        if 0 <= nr < m and 0 <= nc < n and not visited[nr][nc] and grid[nr][nc] == 1:
            visited[nr][nc] = True
            queue.append((nr, nc))
```

Count land cells not reached by BFS:

```python
return sum(
    grid[r][c] == 1 and not visited[r][c]
    for r in range(m)
    for c in range(n)
)
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.numEnclaves([
        [0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]
    ]) == 3

    assert s.numEnclaves([
        [0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]
    ]) == 0

    assert s.numEnclaves([[1]]) == 0
    assert s.numEnclaves([[0,0],[0,1]]) == 0

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| Interior cluster | `3` | Three inland land cells |
| Border-connected | `0` | All land touches the boundary |
| Single land cell at boundary | `0` | It is on the boundary |
| Land cell at corner | `0` | Corner is a boundary cell |