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.

Examples

Example 1:

$$ \begin{array}{|c|c|c|c|} \hline \colorbox{Cerulean} 0 & \colorbox{Cerulean} 0 & \colorbox{Cerulean} 0 & \colorbox{Cerulean} 0 \\ \hline \colorbox{yellow} 1 & \colorbox{Cerulean} 0 & \colorbox{pink} 1 & \colorbox{Cerulean} 0 \\ \hline \colorbox{Cerulean} 0 & \colorbox{pink} 1 & \colorbox{pink} 1 & \colorbox{Cerulean} 0 \\ \hline \colorbox{Cerulean} 0 & \colorbox{Cerulean} 0 & \colorbox{Cerulean} 0 & \colorbox{Cerulean} 0 \\ \hline \end{array} $$

1
2
3
4
5

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:

$$ \begin{array}{|c|c|c|c|} \hline \colorbox{Cerulean} 0 & \colorbox{yellow} 1 & \colorbox{yellow} 1 & \colorbox{Cerulean} 0 \\ \hline \colorbox{Cerulean} 0 & \colorbox{Cerulean} 0 & \colorbox{yellow} 1 & \colorbox{Cerulean} 0 \\ \hline \colorbox{Cerulean} 0 & \colorbox{Cerulean} 0 & \colorbox{yellow} 1 & \colorbox{Cerulean} 0 \\ \hline \colorbox{Cerulean} 0 & \colorbox{Cerulean} 0 & \colorbox{Cerulean} 0 & \colorbox{Cerulean} 0 \\ \hline \end{array} $$

1
2
3
4
5

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.

Solution

Method 1 – DFS to Remove Edge-Connected Land

Intuition

The key idea is to use DFS to “sink” all land cells (1s) that are connected to the boundary of the grid. Any land cell that can reach the boundary is not an enclave. After removing all such cells, the remaining land cells are those that are completely surrounded by sea (0s) and cannot reach the boundary.

Approach

  1. Iterate over all boundary cells (first and last row, first and last column).
  2. For each boundary cell that is land (1), perform DFS to mark all connected land cells as sea (0).
  3. After processing all boundaries, count the number of land cells (1s) left in the grid. These are the enclaves.

Complexity

  • ⏰ Time complexity: O(m * n), where m and n are the grid dimensions, since each cell is visited at most once.
  • 🧺 Space complexity: O(m * n) in the worst case due to the recursion stack.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
public:
    void dfs(vector<vector<int>>& grid, int i, int j) {
        int m = grid.size(), n = grid[0].size();
        if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0) return;
        grid[i][j] = 0;
        dfs(grid, i+1, j);
        dfs(grid, i-1, j);
        dfs(grid, i, j+1);
        dfs(grid, i, j-1);
    }
    int numEnclaves(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; i++) {
            dfs(grid, i, 0);
            dfs(grid, i, n-1);
        }
        for (int j = 0; j < n; j++) {
            dfs(grid, 0, j);
            dfs(grid, m-1, j);
        }
        int ans = 0;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (grid[i][j] == 1) ans++;
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    private static final int[][] DIRS = {{1,0},{-1,0},{0,1},{0,-1}};
    public int numEnclaves(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        for (int i = 0; i < m; i++) {
            dfs(grid, i, 0);
            dfs(grid, i, n-1);
        }
        for (int j = 0; j < n; j++) {
            dfs(grid, 0, j);
            dfs(grid, m-1, j);
        }
        int ans = 0;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (grid[i][j] == 1) ans++;
        return ans;
    }
    private void dfs(int[][] grid, int i, int j) {
        int m = grid.length, n = grid[0].length;
        if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0) return;
        grid[i][j] = 0;
        for (int[] d : DIRS) dfs(grid, i + d[0], j + d[1]);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def numEnclaves(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
        def dfs(i: int, j: int):
            if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == 0:
                return
            grid[i][j] = 0
            for dx, dy in ((1,0),(-1,0),(0,1),(0,-1)):
                dfs(i+dx, j+dy)
        for i in range(m):
            dfs(i, 0)
            dfs(i, n-1)
        for j in range(n):
            dfs(0, j)
            dfs(m-1, j)
        return sum(cell == 1 for row in grid for cell in row)