This approach uses a depth-first search (DFS) to mark land cells connected to the boundaries. We iterate over the boundary cells of the grid and if a land cell is found, we perform DFS to mark all connected land cells as visited. Finally, we count all remaining unvisited land cells inside the grid, which are considered enclaves.
Time Complexity: O(m * n) as each cell is visited at most once.
Space Complexity: O(m * n) in the worst case due to recursion stack used by DFS.
1class Solution:
2 def numEnclaves(self, grid: List[List[int]]) -> int:
3 def dfs(i: int, j: int):
4 if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] == 0:
5 return
6 grid[i][j] = 0
7 dfs(i + 1, j)
8 dfs(i - 1, j)
9 dfs(i, j + 1)
10 dfs(i, j - 1)
11
12 m, n = len(grid), len(grid[0])
13 for i in range(m):
14 if grid[i][0] == 1:
15 dfs(i, 0)
16 if grid[i][n - 1] == 1:
17 dfs(i, n - 1)
18 for j in range(n):
19 if grid[0][j] == 1:
20 dfs(0, j)
21 if grid[m - 1][j] == 1:
22 dfs(m - 1, j)
23
24 return sum(grid[i][j] for i in range(1, m - 1) for j in range(1, n - 1) if grid[i][j] == 1)
25In this Python implementation, DFS is defined as an inner function. The method iterates over boundary cells, marking connected land cells. Finally, it sums remaining inner land cells (enclaves).
In this approach, we use a queue to perform BFS to mark land cells connected to the boundaries. By enqueueing each boundary land cell and exploring its neighbors iteratively, we can mark all reachable boundary-connected lands. This is followed by counting the unvisited land cells – those are the enclaves.
Time Complexity: O(m * n).
Space Complexity: O(min(m, n)) considering the queue size in the worst case.
1from collections import deque
2
3class Solution:
4 def numEnclaves(self, grid: List[List[int]]) -> int:
5 m, n = len(grid), len(grid[0])
6
7 def bfs(start_i: int, start_j: int):
8 queue = deque([(start_i, start_j)])
9 grid[start_i][start_j] = 0
10 directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
11 while queue:
12 x, y = queue.popleft()
13 for dx, dy in directions:
14 new_x, new_y = x + dx, y + dy
15 if 0 <= new_x < m and 0 <= new_y < n and grid[new_x][new_y] == 1:
16 grid[new_x][new_y] = 0
17 queue.append((new_x, new_y))
18
19 for i in range(m):
20 if grid[i][0] == 1:
21 bfs(i, 0)
22 if grid[i][n - 1] == 1:
23 bfs(i, n - 1)
24
25 for j in range(n):
26 if grid[0][j] == 1:
27 bfs(0, j)
28 if grid[m - 1][j] == 1:
29 bfs(m - 1, j)
30
31 return sum(grid[i][j] == 1 for i in range(m) for j in range(n))
32The Python solution utilizes a deque for breadth-first traversal from the boundary. As it iterates over the boundary cells, deque adds and processes reachable land cells, marking them as explored. Enclaves are counted as left-over land.