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:
