# Number of Enclaves
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-enclaves)
Canonical: https://scaleengineer.com/dsa/problems/number-of-enclaves
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Array, Matrix
---
## Problem
You are given an `m x n` binary matrix `grid`, where `0` represents a sea cell and `1` represents a land cell.

A **move** consists of walking from one land cell to another adjacent (**4-directionally**) land cell or walking off the boundary of the `grid`.

Return _the number of land cells in_ `grid` _for which we cannot walk off the boundary of the grid in any number of **moves**_.

**Example 1:**

![](https://assets.glich.co/dsa/number-of-enclaves/image0.jpg) 

**Input:** grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
**Output:** 3
**Explanation:** There are three 1s that are enclosed by 0s, and one 1 that is not enclosed because its on the boundary.

**Example 2:**

![](https://assets.glich.co/dsa/number-of-enclaves/image1.jpg) 

**Input:** grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
**Output:** 0
**Explanation:** All 1s are either on the boundary or can reach the boundary.

**Constraints:**

* `m == grid.length`
* `n == grid[i].length`
* `1 <= m, n <= 500`
* `grid[i][j]` is either `0` or `1`.

# Approaches
## Brute-Force Search from Every Land Cell
This approach iterates through every cell in the grid. For each land cell (`1`), it performs an independent search (like Depth-First Search or Breadth-First Search) to determine if a path exists from that cell to the grid's boundary. If a cell is a land cell and no such path to the boundary can be found, it is counted as an enclave cell.
**Time:** O((m*n)²) - In the worst-case scenario, for each of the O(m*n) land cells, we might perform a traversal that visits all O(m*n) cells. This results in a quadratic time complexity. · **Space:** O(m*n) - For each check, a `visited` matrix of size m*n is created. The queue used for BFS can also grow up to O(m*n) in the worst case.
**Pros:** Conceptually straightforward, as it directly translates the question: 'for each land cell, can it reach the boundary?'
**Cons:** Extremely inefficient due to massive redundant computations.; Traverses the same group of connected land cells multiple times, once for each cell in that group.; Likely to result in a 'Time Limit Exceeded' error on larger inputs.
### Explanation
The algorithm proceeds cell by cell. For every single land cell, we initiate a new traversal to check its connectivity to the boundary. This leads to a lot of repeated work, as cells belonging to the same island will be re-explored multiple times.

```java
class Solution {
    public int numEnclaves(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int enclaveCount = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    if (!canReachBoundary(grid, i, j, m, n)) {
                        enclaveCount++;
                    }
                }
            }
        }
        return enclaveCount;
    }

    private boolean canReachBoundary(int[][] grid, int r, int c, int m, int n) {
        boolean[][] visited = new boolean[m][n];
        java.util.Queue<int[]> queue = new java.util.LinkedList<>();
        
        queue.offer(new int[]{r, c});
        visited[r][c] = true;

        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};

        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int row = cell[0];
            int col = cell[1];

            if (row == 0 || row == m - 1 || col == 0 || col == n - 1) {
                return true; // Found a path to the boundary
            }

            for (int i = 0; i < 4; i++) {
                int newRow = row + dr[i];
                int newCol = col + dc[i];

                if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n &&
                    grid[newRow][newCol] == 1 && !visited[newRow][newCol]) {
                    visited[newRow][newCol] = true;
                    queue.offer(new int[]{newRow, newCol});
                }
            }
        }
        return false; // No path to the boundary found
    }
}
```
### Algorithm
*   Initialize `enclave_count = 0`.
*   Iterate through each cell `(r, c)` of the grid.
*   If `grid[r][c]` is `1`:
    *   Perform a traversal (e.g., BFS) starting from `(r, c)` to see if it can reach a boundary cell. This requires a new `visited` array for each starting cell.
    *   During the traversal, if any visited cell is on the boundary, we know the starting cell `(r, c)` can escape.
    *   If the entire traversal completes without finding a path to the boundary, the starting cell `(r, c)` is an enclave cell. Increment `enclave_count`.
*   Return `enclave_count`.

## Boundary Traversal (DFS/BFS)
This is a much more efficient approach. The core idea is that any land cell connected to a land cell on the boundary can also reach the boundary. Therefore, these cells are not part of an enclave. We can find all such cells by starting a traversal from the boundary land cells and 'sinking' or marking all connected land cells. The remaining, unmarked land cells are the ones that form enclaves.
**Time:** O(m * n) - In the worst case, the traversal (DFS/BFS) visits every cell in the grid once. The initial boundary scan and the final count also take O(m*n) time, leading to a linear time complexity overall. · **Space:** O(m * n) - This is the worst-case space complexity for the recursion call stack in DFS. If the grid contains a long, winding path of land cells, the recursion depth can be proportional to the total number of cells. Using an iterative BFS would have the same worst-case space for its queue.
**Pros:** Optimal time complexity of O(m*n).; Elegant and efficient logic by inverting the problem.; Avoids an explicit auxiliary `visited` matrix by modifying the input grid, which can be a space optimization.
**Cons:** Modifies the input grid, which might not be desirable in all scenarios. A copy would be needed if the original grid must be preserved, increasing space usage.; The recursion stack can still lead to a StackOverflowError on grids with very deep paths.
### Explanation
Instead of checking from the inside out, we work from the outside in. We assume all land cells are enclaves, and then we disqualify any land cell that can touch the boundary. By starting our search from the boundary, we can find and mark all such 'non-enclave' cells in a single pass.

```java
class Solution {
    public int numEnclaves(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        // Start DFS from all '1's on the boundary to mark them and their connected components.
        for (int i = 0; i < m; i++) {
            // First column
            if (grid[i][0] == 1) {
                dfs(grid, i, 0);
            }
            // Last column
            if (grid[i][n - 1] == 1) {
                dfs(grid, i, n - 1);
            }
        }

        for (int j = 0; j < n; j++) {
            // First row
            if (grid[0][j] == 1) {
                dfs(grid, 0, j);
            }
            // Last row
            if (grid[m - 1][j] == 1) {
                dfs(grid, m - 1, j);
            }
        }

        // Count the remaining '1's, which are the enclaves.
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    count++;
                }
            }
        }
        return count;
    }

    private void dfs(int[][] grid, int r, int c) {
        int m = grid.length;
        int n = grid[0].length;

        if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] != 1) {
            return;
        }

        // Mark the cell as visited by 'sinking' it.
        grid[r][c] = 0;

        // Explore 4-directionally.
        dfs(grid, r + 1, c);
        dfs(grid, r - 1, c);
        dfs(grid, r, c + 1);
        dfs(grid, r, c - 1);
    }
}
```
### Algorithm
*   Iterate over the cells on the four boundaries of the grid (top, bottom, left, right).
*   If a boundary cell is a land cell (`1`), start a traversal (DFS or BFS) from this cell.
*   The traversal finds all connected land cells. To mark these cells as 'visited' and 'connected to the boundary', we modify the grid in-place, changing their value from `1` to `0` (effectively 'sinking' them).
*   After the traversals from all boundary land cells are complete, the grid is modified such that only the true enclave cells remain as `1`.
*   Finally, iterate through the entire modified grid and count the number of remaining `1`s. This count is the final answer.

# Solutions
### Java

```java
class Solution {
private
  int m;
private
  int n;
private
  int[][] grid;
public
  int numEnclaves(int[][] grid) {
    this.grid = grid;
    m = grid.length;
    n = grid[0].length;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == 1 && (i == 0 || i == m - 1 || j == 0 || j == n - 1)) {
          dfs(i, j);
        }
      }
    }
    int ans = 0;
    for (var row : grid) {
      for (var v : row) {
        ans += v;
      }
    }
    return ans;
  }
private
  void dfs(int i, int j) {
    grid[i][j] = 0;
    int[] dirs = {-1, 0, 1, 0, -1};
    for (int k = 0; k < 4; ++k) {
      int x = i + dirs[k], y = j + dirs[k + 1];
      if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {
        dfs(x, y);
      }
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numEnclaves(vector<vector<int>> &grid) {
    int m = grid.size(), n = grid[0].size();
    int dirs[5] = {-1, 0, 1, 0, -1};
    function<void(int, int)> dfs = [&](int i, int j) {
      grid[i][j] = 0;
      for (int k = 0; k < 4; ++k) {
        int x = i + dirs[k], y = j + dirs[k + 1];
        if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y]) {
          dfs(x, y);
        }
      }
    };
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] && (i == 0 || i == m - 1 || j == 0 || j == n - 1)) {
          dfs(i, j);
        }
      }
    }
    int ans = 0;
    for (auto &row : grid) {
      for (auto &v : row) {
        ans += v;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def numEnclaves(self, grid: List[List[int]]) -> int: def dfs(i, j): grid[i][j] = 0 for a, b in pairwise(dirs): x, y = i + a, j + b if 0 <= x < m and 0 <= y < n and grid[x][y]: dfs(x, y) m, n = len(grid), len(grid[0]) dirs = (- 1, 0, 1, 0, - 1) for i in range(m): for j in range(n): if grid[i][j] and (i == 0 or i == m - 1 or j == 0 or j == n - 1): dfs(i, j) return sum(v for row in grid for v in row)

```