Number of Closed Islands Problem
Problem
Given a 2D grid
consists of 0s
(land) and 1s
(water). An island is a maximal 4-directionally connected group of 0s
and a closed island is an island totally (all left, top, right, bottom) surrounded by 1s.
Return the number of closed islands.
Examples
Example 1:
|
|
Example 2:
|
|
Example 3:
|
|
Constraints:
1 <= grid.length, grid[0].length <= 100
0 <= grid[i][j] <=1
Solution
Method 1 – BFS Flood Fill
Intuition
A closed island is a group of 0s completely surrounded by 1s (including the grid boundary). We can use BFS to flood fill all 0s connected to the boundary, then count the number of remaining closed islands by BFS.
Approach
- Flood fill all 0s connected to the boundary (turn them to 1) using BFS.
- For each cell inside the grid, if it is 0, start a BFS to mark all connected 0s as visited (turn to 1) and increment the count.
- Return the count of closed islands found.
Code
C++
|
|
Go
|
|
Java
|
|
Kotlin
|
|
Python
|
|
Rust
|
|
TypeScript
|
|
Complexity
- ⏰ Time complexity:
O(m * n)
, since each cell is visited at most once. - 🧺 Space complexity:
O(m * n)
, for the queue and visited marking