Number of Islands medium

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.

Example 1:

Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] Output: 1

Example 2:

Input: grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] Output: 3

Steps to Solve

1. Initialization: Initialize a count variable to 0 (this will store the number of islands).
2. Iteration: Iterate through each cell of the grid.
3. Island Detection: If a cell contains '1' (land) and hasn't been visited yet:
   • Increment the count (we've found a new island).
   • Perform Depth-First Search (DFS) or Breadth-First Search (BFS) starting from this cell to mark all connected land cells as visited.
4. DFS/BFS: The DFS/BFS function explores adjacent land cells recursively/iteratively, marking them as visited (e.g., changing their value to '0' or using a separate visited matrix). This ensures we don't recount the same island multiple times.
5. Return Count: After iterating through the entire grid, return the count.

Explanation

The key idea is to use Depth-First Search (DFS) or Breadth-First Search (BFS) to explore connected components of land. When we find a '1' (land), we know we've encountered a new island. The DFS/BFS ensures we explore all connected land cells before moving on to other potential islands. By marking cells as visited, we prevent double-counting.

Code (Python using DFS)

def numIslands(grid):
    """
    Finds the number of islands in a grid.

    Args:
      grid: A list of lists representing the grid.

    Returns:
      The number of islands.
    """

    rows = len(grid)
    if rows == 0:
        return 0
    cols = len(grid[0])
    count = 0

    def dfs(row, col):
        if row < 0 or row >= rows or col < 0 or col >= cols or grid[row][col] == '0':
            return
        grid[row][col] = '0'  # Mark as visited
        dfs(row + 1, col)
        dfs(row - 1, col)
        dfs(row, col + 1)
        dfs(row, col - 1)

    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == '1':
                count += 1
                dfs(i, j)

    return count

Complexity Analysis

• Time Complexity: O(M * N), where M and N are the number of rows and columns in the grid. We visit each cell at most once.
• Space Complexity: O(M * N) in the worst case (using DFS). This is because the recursion stack depth in DFS could reach up to the size of the largest island, which could be the entire grid in the worst case. A BFS approach would use a queue whose size can be, at most, O(M*N) in the worst-case scenario (a single giant island). However, if we use an in-place modification of the input grid to mark visited cells, we can reduce the space complexity to O(1).