Number of Enclaves
Description
You are given an m × n binary matrix grid, where 0 represents a sea cell and 1 represents a land cell.
From any land cell, you can walk to another adjacent land cell (up, down, left, or right — no diagonal movement). You can also walk off the boundary of the grid if you are on a border cell.
Your task is to return the number of land cells from which it is impossible to walk off the boundary of the grid in any number of moves.
In other words, count the land cells that are completely enclosed — surrounded by sea or by other enclosed land, with no chain of connected land cells leading to any edge of the grid. These trapped land cells are called enclaves.
Examples
Example 1
Input: grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
Output: 3
Explanation: There are four land cells in total: (1,0), (1,2), (2,1), and (2,2). Cell (1,0) is on the left boundary of the grid, so it can walk off — it is NOT an enclave. The remaining three land cells — (1,2), (2,1), and (2,2) — are connected to each other but completely surrounded by sea cells. No chain of land cells connects them to any edge of the grid, so all three are enclaves.
Example 2
Input: grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
Output: 0
Explanation: The land cells are (0,1), (0,2), (1,2), and (2,2). Cells (0,1) and (0,2) are on the top boundary (row 0), so they can walk off the grid. Cell (1,2) is connected to (0,2) via an adjacent land link, so it can also reach the boundary. Cell (2,2) is connected to (1,2), which connects to the boundary. Every land cell either sits on the boundary or has a land-cell path to the boundary. There are zero enclaves.
Constraints
- m == grid.length
- n == grid[i].length
- 1 ≤ m, n ≤ 500
- grid[i][j] is either 0 or 1
Editorial
Brute Force
Intuition
The most direct way to solve this problem is to ask the question for each land cell individually: "Can this cell reach the boundary?"
For every land cell, we start a fresh BFS (or DFS). From that cell, we explore all connected land cells. If at any point during the exploration we reach a cell that sits on the boundary (row 0, last row, column 0, or last column), we know the starting cell CAN escape — it is NOT an enclave. If the entire connected component is explored without ever touching the boundary, the starting cell is an enclave.
Think of it like being dropped into an island on a map and trying to walk to the ocean. You check every connected piece of land. If you never reach the coastline (grid boundary), you are landlocked.
The critical inefficiency here is that we start a completely new search for every single land cell, even though cells in the same connected component share the same answer. We throw away all the exploration work after each cell.
Step-by-Step Explanation
Let's trace through with grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]:
Land cells: (1,0), (1,2), (2,1), (2,2). We check each one independently.
Step 1: Check cell (1,0).
- Start BFS from (1,0).
- (1,0) is on the boundary (column 0). Immediately: CAN escape.
- Result: NOT an enclave.
- enclave_count = 0
Step 2: Check cell (1,2).
- Start a completely fresh BFS from (1,2). visited = {(1,2)}.
- (1,2) is NOT on the boundary. Explore neighbors:
- (0,2) = 0 (sea), skip.
- (2,2) = 1 (land, unvisited), add to queue. visited = {(1,2), (2,2)}.
- (1,1) = 0 (sea), skip.
- (1,3) = 0 (sea), skip.
- Dequeue (2,2). NOT on boundary. Explore neighbors:
- (1,2) = visited, skip.
- (3,2) = 0 (sea), skip.
- (2,1) = 1 (land, unvisited), add. visited = {(1,2), (2,2), (2,1)}.
- (2,3) = 0 (sea), skip.
- Dequeue (2,1). NOT on boundary. Explore neighbors:
- (1,1) = 0, skip. (3,1) = 0, skip. (2,0) = 0, skip. (2,2) = visited, skip.
- Queue empty. Never reached boundary.
- Result: (1,2) IS an enclave.
- enclave_count = 1
Step 3: Check cell (2,1).
- Start another completely fresh BFS from (2,1). (All previous work discarded!)
- Explore (2,1) → (2,2) → (1,2). Same connected component. Never reaches boundary.
- Result: (2,1) IS an enclave.
- enclave_count = 2
Step 4: Check cell (2,2).
- Yet another fresh BFS. Same component. Same result.
- Result: (2,2) IS an enclave.
- enclave_count = 3
Final Answer: 3
Notice: We explored the exact same connected component {(1,2), (2,1), (2,2)} three separate times — once for each cell in the component. This is the core redundancy.
Algorithm
- Initialize enclave_count = 0.
- For each cell (i, j) in the grid:
- If grid[i][j] == 1 (land):
- Create a fresh visited set and BFS queue.
- BFS from (i, j), exploring all connected land cells.
- If any cell in the BFS touches the boundary → NOT an enclave.
- If BFS finishes without touching boundary → enclave_count += 1.
- If grid[i][j] == 1 (land):
- Return enclave_count.
Code
class Solution {
public:
int numEnclaves(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
int count = 0;
int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
queue<pair<int,int>> q;
vector<vector<bool>> visited(m, vector<bool>(n, false));
q.push({i, j});
visited[i][j] = true;
bool canEscape = false;
while (!q.empty() && !canEscape) {
auto [r, c] = q.front();
q.pop();
if (r == 0 || r == m-1 || c == 0 || c == n-1) {
canEscape = true;
break;
}
for (auto& d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n
&& grid[nr][nc] == 1 && !visited[nr][nc]) {
visited[nr][nc] = true;
q.push({nr, nc});
}
}
}
if (!canEscape) count++;
}
}
}
return count;
}
};from collections import deque
class Solution:
def numEnclaves(self, grid: list[list[int]]) -> int:
m, n = len(grid), len(grid[0])
count = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
visited = set()
queue = deque([(i, j)])
visited.add((i, j))
can_escape = False
while queue and not can_escape:
r, c = queue.popleft()
if r == 0 or r == m - 1 or c == 0 or c == n - 1:
can_escape = True
break
for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
nr, nc = r + dr, c + dc
if (0 <= nr < m and 0 <= nc < n
and grid[nr][nc] == 1
and (nr, nc) not in visited):
visited.add((nr, nc))
queue.append((nr, nc))
if not can_escape:
count += 1
return countclass Solution {
public int numEnclaves(int[][] grid) {
int m = grid.length, n = grid[0].length;
int count = 0;
int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
boolean[][] visited = new boolean[m][n];
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{i, j});
visited[i][j] = true;
boolean canEscape = false;
while (!queue.isEmpty() && !canEscape) {
int[] cell = queue.poll();
int r = cell[0], c = cell[1];
if (r == 0 || r == m-1 || c == 0 || c == n-1) {
canEscape = true;
break;
}
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n
&& grid[nr][nc] == 1
&& !visited[nr][nc]) {
visited[nr][nc] = true;
queue.offer(new int[]{nr, nc});
}
}
}
if (!canEscape) count++;
}
}
}
return count;
}
}Complexity Analysis
Time Complexity: O(K × m × n), where K is the number of land cells
For each of the K land cells, we start a fresh BFS that can visit up to O(m × n) cells in the worst case. If the entire grid is land (K = m × n), this becomes O((m × n)²). With m, n up to 500, that is 500² × 500² = 6.25 × 10^10 operations — far too slow.
Space Complexity: O(m × n)
Each BFS creates a visited matrix of size m × n. The BFS queue can also hold up to O(m × n) cells. Since we discard and recreate these for every land cell, the peak space at any one time is O(m × n).
Why This Approach Is Not Efficient
The brute force approach wastes enormous effort by re-exploring the same connected components. In Example 1, cells (1,2), (2,1), and (2,2) all belong to the same island. Yet we run a full BFS three times — once per cell — and each time we discover the same three cells and reach the same conclusion.
With m = n = 500, the grid can have up to 250,000 land cells. If they form one large connected component, each BFS scans all 250,000 cells, giving 250,000 × 250,000 = 6.25 × 10^10 operations. This is far beyond any reasonable time limit.
The key insight is to reverse the problem. Instead of asking "can this cell reach the boundary?" for every interior cell, ask: "which cells are reachable FROM the boundary?" Start from all boundary land cells and flood fill inward. Any land cell NOT reached by this flood fill is an enclave. This processes every cell at most once — O(m × n) total.
Optimal Approach - Boundary Flood Fill (BFS)
Intuition
Instead of searching outward from each interior cell, we flip the perspective: search inward from the boundary.
Imagine the grid is a fenced island surrounded by ocean. The grid boundary is the coastline. Any land cell on the coastline can obviously "escape" into the ocean. And any land cell connected to a coastline cell through a chain of land cells can also escape.
So the strategy is:
- Walk along the entire boundary of the grid.
- For every land cell on the boundary, start a BFS that spreads inward through all connected land cells.
- Every cell reached by this BFS is "safe" — it can reach the boundary. Mark it.
- After processing all boundary land cells, scan the grid. Any land cell that was NOT marked is an enclave — it has no path to the boundary.
This is sometimes called boundary flood fill. By starting from the boundary, we guarantee that every reachable cell is found in a single pass. The cells left behind are exactly the enclaves.
We can implement the marking by simply setting boundary-reachable land cells to 0 (converting them to sea). Then counting the remaining 1s gives us the number of enclaves.
Step-by-Step Explanation
Let's trace through with grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]:
Step 1: Scan the boundary for land cells.
- Top row (row 0): (0,0)=0, (0,1)=0, (0,2)=0, (0,3)=0. No land.
- Bottom row (row 3): (3,0)=0, (3,1)=0, (3,2)=0, (3,3)=0. No land.
- Left column (col 0): (0,0)=0, (1,0)=1 ← LAND!, (2,0)=0, (3,0)=0.
- Right column (col 3): (0,3)=0, (1,3)=0, (2,3)=0, (3,3)=0. No land.
- Boundary land cells found: [(1,0)]. Enqueue all of them.
Step 2: Mark (1,0) as safe. Set grid[1][0] = 0.
- Grid: [[0,0,0,0],[0,0,1,0],[0,1,1,0],[0,0,0,0]]
Step 3: BFS from (1,0). Dequeue (1,0). Check 4 neighbors:
- (0,0) = 0 (sea), skip.
- (2,0) = 0 (sea), skip.
- (1,1) = 0 (sea), skip.
- No land neighbors found. Nothing new to enqueue.
Step 4: Queue is empty. BFS complete. Cell (1,0) was an isolated boundary land cell with no connected interior land.
Step 5: Count remaining land cells. Scan the entire grid:
- (1,2) = 1 → enclave!
- (2,1) = 1 → enclave!
- (2,2) = 1 → enclave!
- All other cells are 0.
Step 6: Return 3.
The three cells (1,2), (2,1), and (2,2) form a connected island that has no land-cell path to any edge of the grid. They are completely enclosed.
Boundary Flood Fill — Eliminate Reachable Land, Count the Rest — Watch how BFS starts from boundary land cells, marks all connected land as 'safe', and then counts the remaining unmarked land cells as enclaves.
Algorithm
- Create a BFS queue.
- Scan all boundary cells (top row, bottom row, left column, right column):
- For each boundary cell (i, j) where grid[i][j] == 1:
- Set grid[i][j] = 0 (mark as safe/sea).
- Enqueue (i, j).
- For each boundary cell (i, j) where grid[i][j] == 1:
- BFS inward from all boundary land cells:
- While the queue is not empty:
- Dequeue cell (r, c).
- For each of the 4 neighbors (nr, nc):
- If (nr, nc) is within bounds and grid[nr][nc] == 1:
- Set grid[nr][nc] = 0 (mark as safe).
- Enqueue (nr, nc).
- If (nr, nc) is within bounds and grid[nr][nc] == 1:
- While the queue is not empty:
- Count remaining land: Iterate over the entire grid and count cells where grid[i][j] == 1. These are the enclaves.
- Return the count.
Code
class Solution {
public:
int numEnclaves(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
queue<pair<int,int>> q;
int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
// Enqueue all boundary land cells
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.push({i, j});
grid[i][j] = 0;
}
}
}
// BFS to mark all boundary-reachable land
while (!q.empty()) {
auto [r, c] = q.front();
q.pop();
for (auto& d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n
&& grid[nr][nc] == 1) {
grid[nr][nc] = 0;
q.push({nr, nc});
}
}
}
// Count remaining land cells (enclaves)
int count = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (grid[i][j] == 1) count++;
return count;
}
};from collections import deque
class Solution:
def numEnclaves(self, grid: list[list[int]]) -> int:
m, n = len(grid), len(grid[0])
q = deque()
# Enqueue all boundary land cells
for i in range(m):
for j in range(n):
if (i == 0 or i == m - 1 or j == 0 or j == n - 1) \
and grid[i][j] == 1:
q.append((i, j))
grid[i][j] = 0
# BFS to mark all boundary-reachable land
while q:
r, c = q.popleft()
for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n \
and grid[nr][nc] == 1:
grid[nr][nc] = 0
q.append((nr, nc))
# Count remaining land cells (enclaves)
return sum(
grid[i][j]
for i in range(m)
for j in range(n)
)class Solution {
public int numEnclaves(int[][] grid) {
int m = grid.length, n = grid[0].length;
Queue<int[]> queue = new LinkedList<>();
int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
// Enqueue all boundary land cells
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) {
queue.offer(new int[]{i, j});
grid[i][j] = 0;
}
}
}
// BFS to mark all boundary-reachable land
while (!queue.isEmpty()) {
int[] cell = queue.poll();
int r = cell[0], c = cell[1];
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n
&& grid[nr][nc] == 1) {
grid[nr][nc] = 0;
queue.offer(new int[]{nr, nc});
}
}
}
// Count remaining land cells (enclaves)
int count = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (grid[i][j] == 1) count++;
return count;
}
}Complexity Analysis
Time Complexity: O(m × n)
We perform three linear passes over the grid:
- Boundary scan: O(m + n) to walk the perimeter.
- BFS: Each cell is enqueued and processed at most once. The BFS visits at most O(m × n) cells total.
- Final count: O(m × n) to scan all cells.
The dominant cost is O(m × n). This is optimal because we must examine every cell at least once to determine the answer.
Space Complexity: O(m × n)
The BFS queue can contain up to O(m × n) cells in the worst case (e.g., if all boundary cells are land and all interior cells are land, the queue initially holds the entire perimeter and then processes the interior). The algorithm modifies the input grid in-place, so no additional grid copy is needed. If the input cannot be modified, a separate visited matrix of size O(m × n) would be required.