Solution For Number Of Closed Islands

Problem Statement:
Given a 2D grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example:
Input:
11000
11000
00100
00011
Output: 3

Solution Approach:
DFS or Depth-First Search is used to solve this Number of Closed Islands problem. We traverse the entire matrix and check for ‘1’s or lands, and whenever we encounter one, we perform a DFS that visits all the connected landmasses and marks them as visited so that we don’t consider them again. By running this DFS, we are essentially iterating over each island, and we maintain a count of how many visited islands we have.

Here is what our solution approach will look like:

1. Set a variable to store the count of visited islands to 0
2. Traverse the entire grid matrix
   a. Check for ‘1’s i.e if we encounter land that has not been visited yet
   i. Increment the count of visited islands
   ii. Mark all adjacent lands as visited using DFS
   b. If we encounter ‘0’s i.e water or if we encounter land that has already been visited, then we move on to the next cell
3. Return the count of visited islands

Let’s take a look at the implementation in Python code.

Solution Code:

class Solution:
def numIslands(self, grid: List[List[str]]) -> int:

    def dfs(row, col):
        # Mark current cell as visited
        self.visited[row][col] = True
        # Check all 4 directions for adjacent lands
        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            r = row + dr
            c = col + dc
            # Check if adjancet cell is within bounds and is land that hasn't been visited 
            if r >= 0 and r < self.rows and c >= 0 and c < self.cols and not self.visited[r][c] and self.grid[r][c] == '1':
                # Visit adjacent land as well
                dfs(r,c)

    self.rows = len(grid)
    self.cols = len(grid[0])
    self.grid = grid
    self.visited = [[False for _ in range(self.cols)] for _ in range(self.rows)]

    count = 0
    for row in range(self.rows):
        for col in range(self.cols):
            # Check for land that hasn't been visited yet
            if not self.visited[row][col] and self.grid[row][col] == '1':
                count += 1
                # Visit all connected land masses with DFS
                dfs(row, col)

    return count

Time Complexity Analysis:
Traversing the entire matrix adds up to O(mn) time complexity where m and n are the number of rows and columns in the grid.
In addition to this, we perform a DFS for each unvisited cell which is again O(mn) time complexity in the worst case when the entire matrix is filled with ‘1’s or land.
Therefore, the overall time complexity is O(mn)².
The space complexity is also O(mn)² because of the recursion stack.

Step by Step Implementation For Number Of Closed Islands

class Solution {
    public int closedIsland(int[][] grid) {
        int count = 0;
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if(grid[i][j] == 0) {
                    if(dfs(grid, i, j)) {
                        count++;
                    }
                }
            }
        }
        return count;
    }
    
    public boolean dfs(int[][] grid, int i, int j) {
        if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 1) {
            return true;
        }
        grid[i][j] = 1;
        boolean top = dfs(grid, i-1, j);
        boolean bottom = dfs(grid, i+1, j);
        boolean left = dfs(grid, i, j-1);
        boolean right = dfs(grid, i, j+1);
        return top && bottom && left && right;
    }
}

def closedIsland(grid):
        # Iterate through the grid 
        for i in range(len(grid)): 
            for j in range(len(grid[i])): 
                  
                # If the current cell is water 
                # and not visited earlier 
                if (grid[i][j] == 0): 
                      
                    # Perform DFS from this cell 
                    # and find if this DFS path 
                    # reaches any boundary 
                    if (not dfs(grid, i, j)): 
                        return -1
                  
        # Return the count of closed islands 
        return count 
  
# A utility function to do DFS from a given cell 
# (i, j) in the grid. 
def dfs(grid, i, j): 
      
    # If (i, j) is not valid or not water 
    # or already visited 
    if (i < 0 or j < 0 or
        i >= len(grid) or j >= len(grid[0]) or
        grid[i][j] != 0): 
        return False
  
    # Mark this cell as visited 
    grid[i][j] = 1
  
    # Perform DFS in all 4 possible directions 
    # from this cell and increment the count 
    # if this DFS path reaches any boundary 
    if (i == 0 or j == 0 or
        i == len(grid)-1 or j == len(grid[0])-1): 
        global count 
        count += 1
    else: 
        dfs(grid, i+1, j) 
        dfs(grid, i-1, j) 
        dfs(grid, i, j+1) 
        dfs(grid, i, j-1) 
  
    # Return true if this DFS path reaches any boundary 
    return True

There are a number of ways to solve this problem. One approach would be to use a Flood Fill algorithm. We can start at each '0' cell, and perform a flood fill. If the cell is surrounded by '1' cells, then it is part of a closed island. We can keep track of the number of closed islands by incrementing a counter whenever we find a cell that is part of a closed island.

Another approach would be to use a DFS (Depth First Search) algorithm. We can start at each '0' cell, and perform a DFS. If the cell is surrounded by '1' cells, then it is part of a closed island. We can keep track of the number of closed islands by incrementing a counter whenever we find a cell that is part of a closed island.

There are a few ways to solve this problem. One way would be to keep track of all of the closed islands as we iterate through the 2D array. We can do this by using a depth-first search algorithm. For each cell in the 2D array, we check to see if it is an island (i.e. it is not water and it has not been visited before). If it is an island, we increment the closed island counter and then perform a depth-first search on all of its neighbors. The depth-first search will mark all of the cells in the same island as visited, so we will not visit them again. This ensures that we only count each island once.

Another way to solve this problem would be to keep track of the number of water cells that are adjacent to each island cell. We can do this by using a breadth-first search algorithm. For each cell in the 2D array, we check to see if it is an island (i.e. it is not water and it has not been visited before). If it is an island, we increment the island water counter and then perform a breadth-first search on all of its neighbors. The breadth-first search will mark all of the cells in the same island as visited, so we will not visit them again. This ensures that we only count each island once.

public class Solution {
    public int ClosedIsland(int[][] grid) {
        
        int count = 0;
        
        for(int i = 0; i < grid.Length; i++)
        {
            for(int j = 0; j < grid[i].Length; j++)
            {
                if(grid[i][j] == 0)
                {
                    if(DFS(grid, i, j))
                    {
                        count++;
                    }
                }
            }
        }
        
        return count;
    }
    
    public bool DFS(int[][] grid, int i, int j)
    {
        if(i < 0 || i >= grid.Length || j < 0 || j >= grid[i].Length || grid[i][j] == 1)
        {
            return true;
        }
        
        grid[i][j] = 1;
        
        bool up = DFS(grid, i - 1, j);
        bool down = DFS(grid, i + 1, j);
        bool left = DFS(grid, i, j - 1);
        bool right = DFS(grid, i, j + 1);
        
        return up && down && left && right;
    }
}