Number of Closed Islands
Leetcode Daily Challenge (6th April, 2023)
Problem Statement:-
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.
Link: https://leetcode.com/problems/number-of-closed-islands/
Problem Explanation with examples:-
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
Example 2
Input: grid = [[0,0,1,0,0],
[0,1,0,1,0],
[0,1,1,1,0]]
Output: 1
Example 3
Input: grid = [[1,1,1,1,1,1,1],
[1,0,0,0,0,0,1],
[1,0,1,1,1,0,1],
[1,0,1,0,1,0,1],
[1,0,1,1,1,0,1],
[1,0,0,0,0,0,1],
[1,1,1,1,1,1,1]]
Output: 2
Constraints
1 <= grid.length, grid[0].length <= 1000 <= grid[i][j] <=1
Intuition:-
For each cell in the grid, if it is 0 and not visited, then we check if it is closed using dfs.
Call dfs on the cell and if it returns True, then we increment count by 1.
In dfs, if the cell is out of bounds or visited, then we return True.
If the cell is 1, then we return True.
Else, we set isClosed to True and call dfs on the 4 adjacent cells.
Solution:-
Initialize m to the number of rows in the grid and n to the number of columns in the grid.
Initialize count to 0 and visited to a 2D array of size m * n with all elements set to False.
Define dfs as follows:
If the cell is out of bounds or visited, then we return True.
If the cell is 1, then we return True.
Else, we set isClosed to True and call dfs on the 4 adjacent cells.
Return isClosed at the end.
For each cell in the grid, if it is 0 and not visited, then we check if it is closed using dfs.
Call dfs on the cell and if it returns True, then we increment count by 1.
Return count at the end.
Code:-
JAVA Solution
public class Solution {
public int closedIsland(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int count = 0;
boolean[][] visited = new boolean[m][n];
boolean dfs(int i, int j) {
if (i < 0 || i >= m || j < 0 || j >= n) {
return false;
}
if (visited[i][j]) {
return true;
}
visited[i][j] = true;
if (grid[i][j] == 1) {
return true;
}
boolean isClosed = true;
isClosed &= dfs(i - 1, j);
isClosed &= dfs(i + 1, j);
isClosed &= dfs(i, j - 1);
isClosed &= dfs(i, j + 1);
return isClosed;
}
for (int i = 1; i < m - 1; i++) {
for (int j = 1; j < n - 1; j++) {
if (grid[i][j] == 0 && !visited[i][j]) {
boolean isClosed = dfs(i, j);
if (isClosed) {
count++;
}
}
}
}
return count;
}
}
Python Solution
class Solution:
def closedIsland(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
count = 0
visited = [[False] * n for _ in range(m)]
def dfs(i, j):
if i < 0 or i >= m or j < 0 or j >= n:
return False
if visited[i][j]:
return True
visited[i][j] = True
if grid[i][j] == 1:
return True
isClosed = True
isClosed &= dfs(i - 1, j)
isClosed &= dfs(i + 1, j)
isClosed &= dfs(i, j - 1)
isClosed &= dfs(i, j + 1)
return isClosed
for i in range(1, m - 1):
for j in range(1, n - 1):
if grid[i][j] == 0 and not visited[i][j]:
isClosed = dfs(i, j)
if isClosed:
count += 1
return count
Complexity Analysis:-
TIME:-
The time complexity is O(m * n) where m is the number of rows in the grid and n is the number of columns in the grid. We visit each cell once.
SPACE:-
The space complexity is O(m * n) where m is the number of rows in the grid and n is the number of columns in the grid. We use a 2D array of size m n to store visited.