200. Number of Islands

number-of-islands.md

200. Number of Islands

from collections import deque

class Solution:
  def numIslands(self, grid: List[List[str]]) -> int:
    # Return 0 if the grid is empty.
    if not grid:
      return 0

    # Get the number of rows and columns in the grid.
    rows, cols = len(grid), len(grid[0])
    
    # Initialize the count of islands to 0.
    count = 0
    
    # Define the possible directions in which we can move from any cell (down, up, left, right).
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    # Define the BFS function. 
    def bfs(r, c):
      # Initialize a queue with the starting cell.
      queue = deque([(r, c)])
      
      # Mark the starting cell as visited.
      grid[r][c] = '2'
      
      # While there are cells to process in the queue.
      while queue:
        # Pop the first cell from the queue.
        row, col = queue.popleft()
        
        # For each of the possible directions.
        for dr, dc in directions:
          # Compute the coordinates of the neighboring cell.
          new_row, new_col = row + dr, col + dc
          
          # If the neighboring cell is within bounds and is a '1', then it's a part of the island.
          if (
            0 <= new_row < rows                 # new row is within bounds
            and 0 <= new_col < cols             # new col is within bounds
            and grid[new_row][new_col] == '1'   # new cell is land
          ):
            # Add it to the queue for further processing.
            queue.append((new_row, new_col))
            
            # Mark it as visited.
            grid[new_row][new_col] = '2'

    # Iterate over each cell in the grid.
    for i in range(rows):
      for j in range(cols):
        # If the cell is a '1', it's a starting point for an island.
        if grid[i][j] == '1':
          # Start BFS from this cell.
          bfs(i, j)
          
          # Once BFS completes, we've explored an entire island, so increment the count.
          count += 1

    # Return the total count of islands.
    return count

For the BFS solution to the "Number of Islands" problem:

1. Time Complexity:

   • We iterate over each cell in the grid exactly once. For each cell that is a '1', we explore its entire island using BFS, marking every visited cell as '2'.
   • As a result, the time complexity is $O(M \times N)$, where $M$ is the number of rows and $N$ is the number of columns. This is because every cell in the grid is visited and processed once.

2. Space Complexity:

   • In the worst case, the queue used in BFS can contain all the cells from the grid if they are all land cells ('1'). However, in practice, the queue will usually contain cells from the perimeter of an island, which would be at most $O(\min(M, N))$. This is because the maximum number of cells you'd typically add to the queue at once would be the cells from the longest row or column in the grid.
   • But, to be on the conservative side, in the worst-case scenario where you have a grid filled with '1's, the space complexity will be $O(M \times N)$.

To summarize:

• Time Complexity: $O(M \times N)$
• Space Complexity: $O(M \times N)$ (worst case) or $O(\min(M, N))$ (typical case)