Given a 2D grid where 0=land and 1=water, return the number of closed islands. A closed island is surrounded by water on all four sides.
Input: [[1,1,1,1,1],[1,0,1,0,1],[1,1,1,1,1]] → Output: 2Input: [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]] → Output: 1
First, DFS from boundary to eliminate land connected to boundary. Then count remaining land components (closed islands).
- DFS from all 0-cells on boundary, mark them as 1 (or visited).
- Then iterate entire grid: if 0 found, DFS to mark whole island, count++.
- Return count.
class Solution {
int m, n;
public int closedIsland(int[][] grid) {
m = grid.length; n = grid[0].length;
// Eliminate boundary-connected land
for (int i = 0; i < m; i++) { dfs(grid,i,0); dfs(grid,i,n-1); }
for (int j = 0; j < n; j++) { dfs(grid,0,j); dfs(grid,m-1,j); }
int count = 0;
for (int i = 1; i < m-1; i++)
for (int j = 1; j < n-1; j++)
if (grid[i][j] == 0) { dfs(grid,i,j); count++; }
return count;
}
private void dfs(int[][] grid, int r, int c) {
if (r<0||r>=m||c<0||c>=n||grid[r][c]!=0) return;
grid[r][c] = 1;
dfs(grid,r+1,c); dfs(grid,r-1,c); dfs(grid,r,c+1); dfs(grid,r,c-1);
}
}
- Time Complexity: O(M*N)
- Space Complexity: O(M*N)