Number Of Closed Islands - Leetcode Solution

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.

1