Number of Enclaves

Share

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.

Example 1
Input: [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]] → Output: 3
Example 2
Input: [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]] → Output: 0

Solution Approach

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.
Java
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)