Number of Islands in Python (Time Complexity: O(M*N))

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. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input:
1 1 1 1 0
1 1 0 1 0
1 1 0 0 0
0 0 0 0 0

Output: 1

Example 2:

Input:
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

Output: 3

Understanding the Problem

The core challenge of this problem is to identify and count distinct islands in a 2D grid. An island is defined as a group of horizontally or vertically connected '1's (land) surrounded by '0's (water). This problem is significant in various applications such as geographical mapping, image processing, and network connectivity.

Potential pitfalls include not correctly handling the boundaries of the grid and not marking visited land cells, which could lead to counting the same island multiple times.

Approach

To solve this problem, we can use Depth-First Search (DFS) or Breadth-First Search (BFS) to traverse the grid. The idea is to iterate through each cell in the grid, and when a '1' is found, initiate a DFS/BFS to mark all connected '1's as visited. This ensures that each island is counted only once.

Naive Solution

A naive solution would involve checking each cell and its neighbors repeatedly, leading to redundant checks and inefficiency. This approach is not optimal due to its high time complexity.

Optimized Solution

The optimized solution involves using DFS or BFS to traverse and mark visited cells. This reduces redundant checks and ensures each cell is processed only once.

DFS Approach

1. Iterate through each cell in the grid. 2. When a '1' is found, increment the island count and initiate a DFS to mark all connected '1's as visited. 3. Continue until all cells are processed.

BFS Approach

1. Similar to DFS, but use a queue to explore neighbors level by level.

Algorithm

Here is a step-by-step breakdown of the DFS algorithm:

Initialize a counter for the number of islands.
Iterate through each cell in the grid.
If a cell contains '1', increment the island counter and initiate a DFS to mark all connected '1's as visited.
In the DFS function, mark the current cell as visited and recursively visit all adjacent cells that contain '1'.
Continue until all cells are processed.

Code Implementation

def numIslands(grid):
    # Helper function for Depth-First Search
    def dfs(grid, i, j):
        # Check for out of bounds or if the cell is water
        if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == '0':
            return
        # Mark the cell as visited by setting it to '0'
        grid[i][j] = '0'
        # Recursively visit all adjacent cells (up, down, left, right)
        dfs(grid, i + 1, j)
        dfs(grid, i - 1, j)
        dfs(grid, i, j + 1)
        dfs(grid, i, j - 1)

    if not grid:
        return 0

    num_islands = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == '1':
                num_islands += 1
                dfs(grid, i, j)
    return num_islands

# Example usage:
grid1 = [
    ["1", "1", "1", "1", "0"],
    ["1", "1", "0", "1", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "0", "0", "0"]
]
print(numIslands(grid1))  # Output: 1

grid2 = [
    ["1", "1", "0", "0", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "1", "0", "0"],
    ["0", "0", "0", "1", "1"]
]
print(numIslands(grid2))  # Output: 3

Complexity Analysis

The time complexity of the DFS approach is O(M*N), where M is the number of rows and N is the number of columns in the grid. This is because each cell is visited once. The space complexity is O(M*N) in the worst case due to the recursion stack.

Edge Cases

Potential edge cases include:

An empty grid.
A grid with no '1's (all water).
A grid with no '0's (all land).

These cases are handled by the algorithm as it checks for grid boundaries and processes each cell appropriately.

Testing

To test the solution comprehensively, include a variety of test cases:

Simple cases with small grids.
Grids with multiple distinct islands.
Grids with complex island shapes.
Edge cases as mentioned above.

Using a testing framework like unittest or pytest can help automate and organize these tests.

Thinking and Problem-Solving Tips

When approaching such problems:

Break down the problem into smaller parts.
Think about how to traverse and mark elements efficiently.
Consider edge cases and how to handle them.
Practice similar problems to improve problem-solving skills.

Conclusion

Understanding and solving the "Number of Islands" problem helps improve skills in grid traversal, graph algorithms, and recursion. Practice and exploration of similar problems can further enhance these skills.

Additional Resources

For further reading and practice: