Number of Islands

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. For example:

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

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

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] is '0' or '1'.

# Number of Islands

This problem asks us to find the number of islands in a 2D grid, where '1' represents land and '0' represents water. An island is formed by connecting adjacent lands horizontally or vertically. We can solve this problem using Depth-First Search (DFS) or Breadth-First Search (BFS).

## Naive Solution (DFS)

The naive solution is to iterate through each cell in the grid. If we find a '1', we increment the island count and then perform a DFS to mark all adjacent land cells as visited (e.g., change them to '0'). This ensures that we don't count the same island multiple times.

```python
def num_islands_naive(grid):
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    island_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':
                island_count += 1
                dfs(i, j)

    return island_count

Optimal Solution (DFS - In-place Modification)

The optimal solution is essentially the same as the naive one, but it's important to clearly articulate the algorithm and its efficiency.

1. Initialization: Iterate through each cell of the grid.
2. Island Detection: If a cell contains '1' (land), increment the island count.
3. Depth-First Search (DFS): Initiate a DFS starting from the current land cell to explore and mark the entire island as visited. This is done by changing the '1's to '0's.
4. Boundary Check: Ensure that the DFS exploration stays within the grid boundaries.

def num_islands(grid):
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    island_count = 0

    def dfs(row, col):
        # Check boundaries and if the cell is land
        if row < 0 or row >= rows or col < 0 or col >= cols or grid[row][col] == '0':
            return

        # Mark the current cell as visited (water)
        grid[row][col] = '0'

        # Explore adjacent cells
        dfs(row + 1, col)  # Down
        dfs(row - 1, col)  # Up
        dfs(row, col + 1)  # Right
        dfs(row, col - 1)  # Left

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

    return island_count

Big(O) Run-time Analysis

The time complexity of this solution is O(M x N), where M is the number of rows and N is the number of columns in the grid.

• We visit each cell in the grid once.
• The DFS function, in the worst case, might visit all the cells in the grid if the entire grid is one island. However, each cell is visited only once because once it's visited, it's marked as '0'.

Big(O) Space Usage Analysis

The space complexity is O(M x N) in the worst-case scenario, where M is the number of rows and N is the number of columns in the grid.

• This is due to the call stack of the DFS function. In the worst-case scenario, where the entire grid is filled with '1's, the DFS function might be called recursively for each cell, leading to a call stack depth of O(M x N).

Edge Cases and Considerations

1. Empty Grid: If the input grid is empty, the function should return 0.
2. Grid with No Islands: If the grid contains only '0's, the function should return 0.
3. Grid with One Large Island: If the entire grid is filled with '1's, the function should return 1.
4. Invalid Input: The grid should only contain '0's and '1's. No other characters are allowed.
5. Large Grids: For extremely large grids, consider using iterative DFS with an explicit stack to avoid potential stack overflow issues.