Number of Enclaves
Medium · Graphs · Array · Depth-First Search · Breadth-First Search · Matrix
Problem
You are given an m x n binary matrix grid, where 0 is sea and 1 is land. From a land cell you may walk to an adjacent (up, down, left, right) land cell, or step off the grid if you are on its boundary.
Return the number of land cells from which you cannot walk off the grid in any number of moves.
Examples
Input: grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]] Output: 3
The three cells in the middle form an island that never touches the edge; the 1 at the left edge can step off.
Input: grid = [[1,1],[1,1]] Output: 0
Every land cell is on the boundary.
Input: grid = [[0,1,0,0],[0,1,1,0],[0,0,1,0],[0,0,0,0]] Output: 0
The island touches the top edge, so all four of its cells can walk off.
Constraints
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 500
- Each grid[i][j] is 0 or 1
Approaches
- Baseline: search from every land cell — time O((m · n)²), space O(m · n)
Follow-up
Flooding from the border answers "which cells can reach the edge" for the whole grid in one pass. The use cases keep that flood and then look at what is left: the largest enclosed island, and how many enclosed islands there are.
Related problems
Start free on Cariara · Coding problems · System design studio
