DSA problem
Number of Enclaves
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 the grid for which we cannot walk off the boundary in any number of moves.
The set of cells that we cannot escape from is exactly the set of land cells that are not connected to any border-adjacent land cell. Equivalently, a land cell is "enclaved" if and only if it cannot reach the border by moving only through 1-cells. Instead of trying to test every cell individually, we flip the perspective: identify the cells that can escape and exclude them.
The optimal approach is a flood-fill from the border. Walk the four edges of the grid; for every 1 cell on the border, run a DFS or BFS that visits every connected land cell and either marks them as visited or zeroes them out in-place. After the flood-fill completes, every remaining 1 in the grid is unreachable from any border, so the answer is the number of remaining 1s.
This costs O(m * n) time because every cell is processed at most twice (once by the flood-fill from the border and once by the final counting pass), and O(m * n) space in the worst case for the recursion/queue depth when the grid is one giant connected land mass.
Examples
grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]3grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]0grid = [[0,0,0,1],[0,1,1,0],[0,1,0,0],[0,0,0,0]]3Constraints
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 500
- grid[i][j] is either 0 or 1.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.