0% completed
Problem Statement
Given an m x n
binary matrix grid, where 0
represents a sea cell and 1
represents a land cell, return the number of land cells
in grid from which you can't reach to the boundary in any number of moves.
In a single move, you can walk from one cell to any cell, which is 4-directionally adjacent to the current cell.
Examples
Example 1:
- Input: grid =
[[0, 0, 0, 1],
[1, 0, 1, 0],
[0, 1, 1, 0],
[0, 0, 0, 0]]
- Output: 3
- Justification: The three land cells in the center, which are at (1, 2), (2, 1), and (2, 2) positions, are surrounded by sea cells and cannot reach the boundary.
Example 2:
- Input: grid =
[[0, 1, 0],
[1, 1, 1],
[0, 1, 0]]
- Output: 0
- Justification: All land cells can connect to the edge either directly or through other land cells.
Example 3:
- Input: grid =
[[0, 0, 0, 0, 0],
[0, 1, 1, 1, 0],
[0, 1, 0, 1, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 0, 0]]
- Output: 8
- Justification: The eight land cells in the middle are surrounded by sea cells and cannot reach the boundary.
Constraints:
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 500
- grid[i][j] is either 0 or 1.
Solution
To solve this problem, we need to find land cells that are completely enclosed by sea cells. Our approach starts by identifying and marking all land cells connected to the boundary. These boundary-connected cells can potentially reach the sea, so we eliminate them from consideration. Next, we count the remaining land cells that are not connected to the boundary. This ensures that we only count land cells that are truly surrounded.
Using Depth-First Search (DFS) for this problem is effective because it allows us to explore and mark all connected land cells starting from any boundary cell. By systematically marking these cells, we can then simply count the unmarked land cells to get our answer. This method ensures we efficiently traverse the grid while accurately identifying and excluding boundary-connected cells.
Step-by-Step Algorithm
To solve the problem of counting land cells that cannot reach the boundary, we can follow these steps:
-
Initialize Variables:
- Get the number of rows (
rows
) and columns (cols
) in the grid. - Define a helper function
dfs
for performing depth-first search.
- Get the number of rows (
-
Mark Boundary-Connected Land Cells:
- Iterate through the first and last columns of each row. If a cell contains land (1), call the
dfs
function to mark all connected land cells as sea (0). - Iterate through the first and last rows of each column. If a cell contains land (1), call the
dfs
function to mark all connected land cells as sea (0).
- Iterate through the first and last columns of each row. If a cell contains land (1), call the
-
Depth-First Search (DFS) Function:
- The
dfs
function should take the grid and the current cell's coordinates (i
,j
) as arguments. - If the cell is out of bounds or is sea (0), return.
- Mark the current cell as sea (0).
- Recursively call
dfs
for the cells to the right, left, down, and up of the current cell.
- The
-
Count Enclaved Land Cells:
- Initialize a variable
count
to 0. - Iterate through each cell in the grid. If a cell contains land (1), increment the
count
.
- Initialize a variable
-
Return the Count:
- Return the final
count
of land cells that cannot reach the boundary.
- Return the final
Algorithm Walkthrough
Let's walk through the example grid:
[[0, 0, 0, 1],
[1, 0, 1, 0],
[0, 1, 1, 0],
[0, 0, 0, 0]]
-
Initialize Variables:
rows = 4
cols = 4
-
Mark Boundary-Connected Land Cells:
- First column:
grid[0][0]
is sea (0).grid[1][0]
is land (1). Calldfs(1, 0)
.- Inside
dfs(1, 0)
: Markgrid[1][0]
as sea (0). - Check down:
dfs(2, 0)
→grid[2][0]
is sea (0). - Check up:
dfs(0, 0)
→grid[0][0]
is sea (0). - Check right:
dfs(1, 1)
→grid[1][1]
is sea (0). - Check left:
dfs(1, -1)
→ Out of bounds.
- Inside
grid[2][0]
is sea (0).grid[3][0]
is sea (0).
- Last column:
grid[0][3]
is land (1). Calldfs(0, 3)
.- Inside
dfs(0, 3)
: Markgrid[0][3]
as sea (0). - Check down:
dfs(1, 3)
→grid[1][3]
is sea (0). - Check up:
dfs(-1, 3)
→ Out of bounds. - Check right:
dfs(0, 4)
→ Out of bounds. - Check left:
dfs(0, 2)
→grid[0][2]
is sea (0).
- Inside
grid[1][3]
is sea (0).grid[2][3]
is sea (0).grid[3][3]
is sea (0).
- First row:
grid[0][0]
is sea (0).grid[0][1]
is sea (0).grid[0][2]
is sea (0).grid[0][3]
is sea (0).
- Last row:
grid[3][0]
is sea (0).grid[3][1]
is sea (0).grid[3][2]
is sea (0).grid[3][3]
is sea (0).
- First column:
-
Count Enclaved Land Cells:
- Initialize
count = 0
. - Iterate through the grid:
grid[0][0]
is sea (0).grid[0][1]
is sea (0).grid[0][2]
is sea (0).grid[0][3]
is sea (0).grid[1][0]
is sea (0).grid[1][1]
is sea (0).grid[1][2]
is land (1). Incrementcount
to 1.grid[1][3]
is sea (0).grid[2][0]
is sea (0).grid[2][1]
is land (1). Incrementcount
to 2.grid[2][2]
is land (1). Incrementcount
to 3.grid[2][3]
is sea (0).grid[3][0]
is sea (0).grid[3][1]
is sea (0).grid[3][2]
is sea (0).grid[3][3]
is sea (0).
- Initialize
-
Return the Count:
- The final
count
of land cells that cannot reach the boundary is 3.
- The final
Therefore, the output for the grid [[0, 0, 0, 1], [1, 0, 1, 0], [0, 1, 1, 0], [0, 0, 0, 0]]
is 3
.
Code
Complexity Analysis
Time Complexity
The time complexity of the provided solution is O(m * n), where m is the number of rows and n is the number of columns in the grid. This is because in the worst case, we might need to visit every cell in the grid once during the DFS traversal.
Space Complexity
The space complexity is O(m * n) as well, considering the recursive call stack during the DFS traversal. In the worst case, the depth of the recursion tree can go up to m * n if the grid is completely filled with land cells.
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible