Number Of Islands - Leetcode Solution

Problem Statement:

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return 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.

Solution:

The given problem is a classic example of a Graph problem where we need to identify different connected components present in the given graph. In this problem, we have a 2D binary grid representing land and water. A connected component, in this case, can be considered as contiguous land surrounded by water.

We can solve this problem using DFS. We can traverse the given matrix cell by cell and every time we encounter land (a cell with a value of 1), we can recursively visit its adjacent cells and mark them as visited. Adjacent cells can be explored recursively using DFS and can be considered as part of the same connected component. We can continue this process till we have visited all the cells in the matrix.

We can initiate a DFS visit every time we encounter unvisited land. This will ensure that we count each connected component only once. We keep track of the number of times we initiate a DFS search, and that will give us the number of islands in the given grid.

Algorithm:

1. Initialize the counter for the number of islands to 0.
2. Traverse the given matrix cell by cell.
3. When we encounter an unvisited cell with a value of 1, initiate a DFS visit.
4. In the DFS visit, mark the current cell as visited and recursively visit its adjacent cells.
5. The adjacent cells to be visited are the cells to the top, bottom, left, and right of the current cell.
6. Keep track of the number of islands visited.
7. Return the number of islands visited.

Let's look at a sample code implementation:

class Solution(object):
    def dfs(self, grid, row, col):
        if row < 0 or col < 0 or row >= len(grid) or col >= len(grid[0]) or grid[row][col] == '0':
            return
        
        grid[row][col] = '0'   # Mark the current cell as visited
        
        # Recursively visit the adjacent cells
        self.dfs(grid, row + 1, col)
        self.dfs(grid, row - 1, col)
        self.dfs(grid, row, col + 1)
        self.dfs(grid, row, col - 1)
        
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if not grid:
            return 0
        
        # Initialize the counter for the number of islands
        num_islands = 0
        
        # Traverse the given matrix cell by cell
        for row in range(len(grid)):
            for col in range(len(grid[0])):
                if grid[row][col] == '1':
                    # We encountered land. Increment the counter and do DFS.
                    num_islands += 1
                    self.dfs(grid, row, col)
        
        # Return the number of islands visited
        return num_islands

Time Complexity: The time complexity of the given algorithm is O(m*n) where m is the number of rows and n is the number of columns in the given matrix.

Space Complexity: The space complexity of the given algorithm is O(m*n) where m is the number of rows and n is the number of columns in the given matrix. This is because in the worst case scenario, the complete matrix could be filled with islands (cells with a value of 1), and we would need to maintain a recursive stack during DFS search, which would be proportional to the total number of islands.

1