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.

Constraints:

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

BFS

The task is straightforward in counting the islands. The biggest pitfall to avoid is not to double count: two nearby land cells $(i_1, j_1)$ and $(i_2, j_2)$ could either be the same island, or two separate islands.

To avoid this, we can “delete” an island by setting all its land cells to water. Then we can simply iterate through all cells and count how many islands there are.

def numIslands(self, grid: List[List[str]]) -> int:
    num_islands = 0

    for i in range(len(grid)):
        for j in range(len(grid[i])):
            if grid[i][j] == "1":
                num_islands += 1
                delete_island(i, j)

    return num_islands

How can we delete an entire island? We can delete land cells by setting them to water, but the hard part is reaching “connected” cells. We can treat the grid as a graph, where each cell is connected by an edge to its adjacent cells. BFS on valid land cells then lets us explore and delete an island.

def is_valid(x: int, y: int) -> bool:
    max_x = len(grid)
    max_y = len(grid[0])

    return 0 <= x < max_x and 0 <= y < max_y

def delete_island(x: int, y: int) -> None:
    """
    Use BFS to set all land nodes connected 
    to the island associated with the cell 
    grid[x][y] to water.
    """
    queue = [(x, y)]
    grid[x][y] = "0"

    while len(queue) > 0:
        (i, j) = queue.pop(0)
        neighbours = [
            (i - 1, j), 
            (i + 1, j), 
            (i, j - 1), 
            (i, j + 1)
        ]

        for k, l in neighbours:
            if is_valid(k, l) and grid[k][l] == "1":
                grid[k][l] = "0"
                queue.append((k, l))

    return None

Putting together the final solution, we have:

def numIslands(self, grid: List[List[str]]) -> int:
    def delete_island(x: int, y: int) -> None:
        """
        Use BFS to set all land nodes connected 
        to this island to water.
        """
        queue = [(x, y)]
        grid[x][y] = "0"

        while len(queue) > 0:
            (i, j) = queue.pop(0)
            neighbours = [
                (i - 1, j), 
                (i + 1, j), 
                (i, j - 1), 
                (i, j + 1)
            ]

            for k, l in neighbours:
                if is_valid(k, l) and grid[k][l] == "1":
                    grid[k][l] = "0"
                    queue.append((k, l))

        return None

    def is_valid(x: int, y: int) -> bool:
        max_x = len(grid)
        max_y = len(grid[0])

        return 0 <= x < max_x and 0 <= y < max_y
    
    num_islands = 0

    for i in range(len(grid)):
        for j in range(len(grid[i])):
            if grid[i][j] == "1":
                num_islands += 1
                delete_island(i, j)

    return num_islands

Time Complexity

The algorithm begins with a loop through the entire grid. Ignoring the BFS function for now, each iteration is constant time and there are $m \times n$ iterations, so the outer loop takes $\mathcal{O}(m \times n)$ time.

Why can we ignore the BFS call? Notice that no matter how many times BFS is called, the total operations cannot exceed a multiple of $m \times n$: each cell is enqueued and dequeued at most once, since if it is a land cell, it is immediately deleted; all other constant time operations can only be called a maximum of $m \times n$ times if delete_island was called at every cell.

Thus, the time complexity of the algorithm is in $\mathcal{O}(m \times n)$.

Space Complexity

Since we edit the grid in-place, we don’t use any extra variables, so space complexity is constant.