In this guide, you will get 1254. Number of Closed Islands LeetCode Solution with the best time and space complexity. The solution to Number of Closed Islands problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
Example 1:
Input: grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
Output: 2
Explanation:
Islands in gray are closed because they are completely surrounded by water (group of 1s).
Example 2:
1254. Number of Closed Islands LeetCode Solution in C++
class Solution {
public:
int closedIsland(vector<vector<int>>& grid) {
const int m = grid.size();
const int n = grid[0].size();
// Remove the lands connected to the edge.
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (i * j == 0 || i == m - 1 || j == n - 1)
if (grid[i][j] == 0)
dfs(grid, i, j);
int ans = 0;
// Reduce to 200. Number of Islands
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (grid[i][j] == 0) {
dfs(grid, i, j);
++ans;
}
return ans;
}
private:
void dfs(vector<vector<int>>& grid, int i, int j) {
if (i < 0 || i == grid.size() || j < 0 || j == grid[0].size())
return;
if (grid[i][j] == 1)
return;
grid[i][j] = 1;
dfs(grid, i + 1, j);
dfs(grid, i - 1, j);
dfs(grid, i, j + 1);
dfs(grid, i, j - 1);
};
}; /* code provided by PROGIEZ */
1254. Number of Closed Islands LeetCode Solution in Java
class Solution {
public int closedIsland(int[][] grid) {
final int m = grid.length;
final int n = grid[0].length;
// Remove the lands connected to the edge.
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (i * j == 0 || i == m - 1 || j == n - 1)
if (grid[i][j] == 0)
dfs(grid, i, j);
int ans = 0;
// Reduce to 200. Number of Islands
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (grid[i][j] == 0) {
dfs(grid, i, j);
++ans;
}
return ans;
}
private void dfs(int[][] grid, int i, int j) {
if (i < 0 || i == grid.length || j < 0 || j == grid[0].length)
return;
if (grid[i][j] == 1)
return;
grid[i][j] = 1;
dfs(grid, i + 1, j);
dfs(grid, i - 1, j);
dfs(grid, i, j + 1);
dfs(grid, i, j - 1);
}
} // code provided by PROGIEZ
1254. Number of Closed Islands LeetCode Solution in Python
class Solution:
def closedIsland(self, grid: list[list[int]]) -> int:
m = len(grid)
n = len(grid[0])
def dfs(i: int, j: int) -> None:
if i < 0 or i == m or j < 0 or j == n:
return
if grid[i][j] == 1:
return
grid[i][j] = 1
dfs(i + 1, j)
dfs(i - 1, j)
dfs(i, j + 1)
dfs(i, j - 1)
# Remove the lands connected to the edge.
for i in range(m):
for j in range(n):
if i * j == 0 or i == m - 1 or j == n - 1:
if grid[i][j] == 0:
dfs(i, j)
ans = 0
# Reduce to 200. Number of Islands
for i in range(m):
for j in range(n):
if grid[i][j] == 0:
dfs(i, j)
ans += 1
return ans # code by PROGIEZ
