Solutions

# DFS or BFS to mark visited land cells.
# graphs

# DFS - O(M*N) time | O(M*N) space
def numIslands(grid: list[list[str]]) -> int:
    islands_count = 0

    for r in range(len(grid)):
        for c in range(len(grid[0])):
            if grid[r][c] == "1":
                mark(r, c, grid)
                islands_count += 1

    return islands_count

def mark(r: int, c: int, grid: list[list[str]]) -> None:
    if r >= len(grid) or c >= len(grid[0]) or r < 0 or c < 0 or grid[r][c] != "1":
        return

    grid[r][c] = "#"
    mark(r+1, c, grid)
    mark(r-1, c, grid)
    mark(r, c+1, grid)
    mark(r, c-1, grid)


# BFS - O(M*N) time | O(min(M,N)) space    
def numIslands(grid: list[list[str]]) -> int:
    islands_count = 0
    nr = len(grid)
    nc = len(grid[0])

    for r in range(len(grid)):
        for c in range(len(grid[0])):
            if grid[r][c] == "1":
                islands_count += 1
                grid[r][c] == "#"
                neighbors = []
                neighbors.append((r,c))
                while neighbors:
                    row, col = neighbors.pop(0)
                    if row-1 >= 0 and grid[row-1][col] == "1":
                        neighbors.append((row-1, col))
                        grid[row -1][col] = "0"
                    if row+1 < nr and grid[row+1][col] == "1":
                        neighbors.append((row+1, col))
                        grid[row+1][col] = "0"
                    if col-1 >=0 and grid[row][col-1] == "1":
                        neighbors.append((row, col-1))
                        grid[row][col-1] = "0"
                    if col+1 < nc and grid[row][col+2] == "1":
                        neighbors.append((row, col+1))
                        grid[row][col+1] = "0"

    return islands_count