Island Counting

December 27, 2023

Problem #

Given a 2D grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.

Solution 1 #

Here’s the Python code to count the number of islands in a 2D grid map, where ‘1’s represent land and ‘0’s represent water:

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

    rows, cols = len(grid), len(grid[0])
    visited = set()
    islands = 0

    def dfs(r, c):
        # If the current cell is out of bounds, water, or already visited, return
        if (r < 0 or r >= rows or c < 0 or c >= cols or
                grid[r][c] == '0' or (r, c) in visited):
            return
        # Mark the cell as visited
        visited.add((r, c))
        # Explore the adjacent cells (up, down, left, right)
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    for r in range(rows):
        for c in range(cols):
            # If the cell is land and not visited, start a DFS from it
            if grid[r][c] == '1' and (r, c) not in visited:
                dfs(r, c)
                islands += 1  # Increment the island count after each DFS

    return islands

# Example usage
grid = [
    ["1", "1", "1", "1", "0"],
    ["1", "1", "0", "1", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "0", "0", "0"]
]
num_islands = numIslands(grid)

In this code:

• A Depth-First Search (DFS) algorithm is used to explore the grid.
• The dfs function is a helper function that marks a cell as visited and recursively explores its adjacent cells (horizontally and vertically).
• For each unvisited land cell (‘1’), we start a new DFS, and after it’s complete, we increment the island count.
• The visited set keeps track of visited cells to avoid revisiting them.

For the given example grid, this code will find that there is 1 island.\

Solution 2 #

Yes, you can certainly use Breadth-First Search (BFS) to solve the problem of counting the number of islands in a 2D grid. BFS can be a good alternative to Depth-First Search (DFS) for this problem, especially in cases where the grid is large, as it may help to avoid stack overflow issues that can occur with deep recursive DFS calls.

Here’s how you can implement the solution using BFS:

1. Iterate over each cell in the grid.
2. When a land cell (‘1’) is found that has not been visited, initiate a BFS from that cell.
3. In the BFS, visit all adjacent land cells, marking them as visited, and add them to the queue to continue the BFS.
4. Once the BFS is complete (no more cells to visit in the queue), increment the count of islands.

I will write the Python code for this approach.

Here’s the Python code for counting the number of islands using Breadth-First Search (BFS):

from collections import deque

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

    rows, cols = len(grid), len(grid[0])
    visited = set()
    islands = 0

    def bfs(r, c):
        queue = deque()
        queue.append((r, c))
        visited.add((r, c))

        while queue:
            row, col = queue.popleft()
            directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]  # Right, Left, Down, Up
            for dr, dc in directions:
                r, c = row + dr, col + dc
                if (0 <= r < rows and 0 <= c < cols and
                        grid[r][c] == '1' and (r, c) not in visited):
                    queue.append((r, c))
                    visited.add((r, c))

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1' and (r, c) not in visited:
                bfs(r, c)
                islands += 1

    return islands

# Example usage
grid_bfs = [
    ["1", "1", "1", "1", "0"],
    ["1", "1", "0", "1", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "0", "0", "0"]
]
num_islands_bfs = numIslandsBFS(grid_bfs)

In this code:

• A Breadth-First Search is initiated for each unvisited land cell found in the grid.
• BFS explores each land cell’s adjacent cells (horizontally and vertically) and marks them as visited, continuing until there are no more cells to visit in the queue.
• The visited set keeps track of visited cells to prevent re-visiting them.
• Each complete BFS traversal marks a new island, so the island count is incremented after each BFS.

For the provided example grid, the code will correctly identify that there is 1 island.

Solution Comparison #

The choice between Depth-First Search (DFS) and Breadth-First Search (BFS) for counting the number of islands in a 2D grid depends on various factors such as the size of the grid, the distribution of land and water cells, and specific performance requirements. Here’s a comparison:

1. Complexity:

   • Both DFS and BFS have a time complexity of (O(M \times N)), where (M) and (N) are the dimensions of the grid. This is because each cell is visited at most once.
   • The space complexity can vary:
     • DFS has a space complexity of (O(M \times N)) in the worst case when the grid is filled with land cells, as it might store the entire grid in the call stack due to recursion.
     • BFS also uses (O(M \times N)) space in the worst case due to the queue, but this is more controlled and predictable than the recursive call stack.

2. Stack Overflow Risk:

   • DFS is implemented recursively and can cause a stack overflow in languages that don’t optimize for tail recursion if the grid is very large or the number of recursive calls is too high.
   • BFS, implemented with a queue, doesn’t have this risk, making it more stable for very large grids.

3. Practical Performance:

   • DFS can be faster in practice for sparse grids (grids with fewer land cells), as it quickly skips water cells and doesn’t require additional space for a queue.
   • BFS might be more efficient in grids with large contiguous areas of land, as it systematically explores adjacent cells.

4. Ease of Implementation:

   • DFS is often considered simpler to implement due to its recursive nature.
   • BFS, while not complex, requires a queue and slightly more bookkeeping.

In summary:

• DFS is typically preferred for its simplicity and potential speed advantages in cases with sparse land cells or smaller grids.
• BFS is a better choice for very large grids or when you want to avoid the risk of stack overflow due to deep recursion.