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

Given a 2d grid map of '1's (land) and '0's (water), find the islands and return an array containing their sizes. An island is surrounded by water and is formed by connecting adjacent land cells horizontally or vertically. You may assume all four edges of the grid are 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: [9]
Explanation:  There is only one island with size 9

Example 2:

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

Output: [1, 4, 2]
Explanation There are three islands with sizes of 1, 4 and 2

Note: The islands' sizes can be returned in any order

Understanding the Problem

The core challenge of this problem is to identify and count the sizes of all 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.

Approach

To solve this problem, we can use Depth-First Search (DFS) or Breadth-First Search (BFS) to explore each island. The idea is to traverse the grid, and whenever we encounter a '1', we initiate a DFS/BFS to mark all connected '1's and count their number, which gives us the size of that island.

Naive Solution

A naive solution would involve checking each cell and performing a DFS/BFS for each '1' found. However, this approach might be inefficient due to repeated traversals of the same cells.

Optimized Solution

An optimized approach involves marking cells as visited during the DFS/BFS traversal to avoid redundant checks. This ensures each cell is processed only once, leading to a time complexity of O(M*N), where M is the number of rows and N is the number of columns in the grid.

Algorithm

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

Initialize an empty list to store the sizes of the islands.
Iterate through each cell in the grid.
When a '1' is found, initiate a DFS to explore the entire island.
During the DFS, mark each visited cell as '0' to avoid revisiting.
Count the number of cells in the island and add the count to the list.

Code Implementation

def numIslands(grid):
    def dfs(grid, i, j):
        # If out of bounds or at a water cell, return 0
        if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == '0':
            return 0
        # Mark the cell as visited
        grid[i][j] = '0'
        # Initialize size of this island
        size = 1
        # Explore all 4 directions
        size += dfs(grid, i + 1, j)
        size += dfs(grid, i - 1, j)
        size += dfs(grid, i, j + 1)
        size += dfs(grid, i, j - 1)
        return size

    if not grid:
        return []

    island_sizes = []
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == '1':
                # Start a DFS for each unvisited land cell
                island_sizes.append(dfs(grid, i, j))
    return island_sizes

# 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: [9]

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: [4, 1, 2]

Complexity Analysis

The time complexity of the DFS approach is O(M*N) because each cell is visited once. The space complexity is O(M*N) in the worst case due to the recursion stack in DFS.

Edge Cases

Potential edge cases include:

Empty grid: The function should return an empty list.
Grid with no land: The function should return an empty list.
Grid with all land: The function should return a list with one element equal to the total number of cells.

Testing

To test the solution comprehensively, consider the following test cases:

Simple grids with one or more islands.
Grids with no islands.
Grids with varying sizes and shapes of islands.

Thinking and Problem-Solving Tips

When approaching such problems, it is crucial to:

Understand the problem requirements and constraints.
Break down the problem into smaller, manageable parts.
Consider different algorithms and their trade-offs.
Practice similar problems to improve problem-solving skills.

Conclusion

Understanding and solving problems like finding the size of islands in a grid is essential for developing strong algorithmic skills. By practicing and exploring different approaches, one can improve their problem-solving abilities and apply these techniques to various real-world scenarios.

Additional Resources

For further reading and practice, consider the following resources: