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.  Islands are formed by connecting adjacent lands horizontally or vertically. We need to count the number of distinct land masses.

## 1. Brute Force Solution (Depth First Search)

A simple approach is to iterate through each cell of the grid.  If we encounter a '1', we increment the island count and then perform a Depth-First Search (DFS) to mark all connected land cells as visited (e.g., by changing them to '0'). This ensures that we don't count the same island multiple times.

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

    rows, cols = len(grid), len(grid[0])
    num_islands = 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
        # Explore adjacent cells
        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':
                num_islands += 1
                dfs(i, j)

    return num_islands

2. Optimal Solution (Depth First Search - In-place Modification)

The brute-force solution is essentially the optimal solution in terms of time complexity. We must visit each cell at least once. The space complexity can be improved slightly (though it remains O(m*n) in worst-case due to recursion depth).

The core idea remains the same: use DFS to explore and mark connected components.

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

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

    return num_islands

3. Big(O) Time Complexity Analysis

• O(m * n), where 'm' is the number of rows and 'n' is the number of columns in the grid.
  • We iterate through each cell in the grid once.
  • The DFS function visits each land cell at most once. In the worst case, the entire grid is land, and DFS will be called for every cell.

4. Big(O) Space Complexity Analysis

• O(m * n) in the worst case due to the call stack of the recursive DFS function.
  • In the worst-case scenario where the entire grid is filled with '1's (land), the DFS function might be called recursively for each cell, leading to a call stack depth proportional to the number of cells.
  • In the average case where islands are small and scattered, the space complexity would be less.

5. Edge Cases and Considerations

• Empty Grid: If the input grid is empty (i.e., grid == None or len(grid) == 0), we should return 0, as there are no islands.
• Grid with No Land: If the grid contains only '0's (water), the algorithm correctly identifies that there are no islands and returns 0.
• Grid with Only One Island: If the entire grid is filled with '1's, the algorithm correctly identifies this as a single island.
• Disconnected Islands: The algorithm correctly handles cases where there are multiple disconnected islands of varying sizes.
• Invalid Input: The problem statement specifies that the grid will only contain '0's and '1's. We could add input validation to check for invalid characters, but it's usually not necessary unless explicitly requested.

6. Alternative Solution: Breadth-First Search (BFS)

Instead of DFS, we could also use BFS to explore connected components. The logic is very similar.

from collections import deque

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

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

    def bfs(row, col):
        queue = deque([(row, col)])
        grid[row][col] = '0'  # Mark starting cell as visited

        while queue:
            r, c = queue.popleft()

            # Explore neighbors
            neighbors = [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]
            for nr, nc in neighbors:
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                    queue.append((nr, nc))
                    grid[nr][nc] = '0'  # Mark as visited

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

    return num_islands

The time and space complexity for BFS are the same as for DFS: O(m*n) in the worst case.