Given a 2D binary matrix where 1 = land and 0 = sea, return the number of land cells that cannot walk off the boundary. A land cell can walk to adjacent land cells.
Input: [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]] → Output: 3Input: [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]] → Output: 0
BFS/DFS from all boundary land cells, marking them as visited. Count remaining unvisited land cells.
- Start BFS/DFS from all 1s on the boundary (row 0, row m-1, col 0, col n-1).
- Mark all reachable land as visited (set to 0 or use visited array).
- Count remaining 1s in the grid.
import java.util.*;
class Solution {
public int numEnclaves(int[][] grid) {
int m = grid.length, n = grid[0].length;
Queue<int[]> q = new LinkedList<>();
for (int i = 0; i < m; i++) for (int j = 0; j < n; j++)
if ((i==0||i==m-1||j==0||j==n-1) && grid[i][j]==1) { q.offer(new int[]{i,j}); grid[i][j]=0; }
int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
while (!q.isEmpty()) {
int[] cur = q.poll();
for (int[] d : dirs) {
int r=cur[0]+d[0], c=cur[1]+d[1];
if (r>=0&&r<m&&c>=0&&c<n&&grid[r][c]==1) { grid[r][c]=0; q.offer(new int[]{r,c}); }
}
}
int count = 0;
for (int[] row : grid) for (int v : row) count += v;
return count;
}
}
- Time Complexity: O(M*N)
- Space Complexity: O(M*N)