Understanding the Problem
The core challenge of this problem is to identify and measure the size of each island in a 2D grid. An island is defined as a group of connected '1's (land) surrounded by '0's (water). The connection can be horizontal or vertical but not diagonal.
This problem is significant in various applications such as image processing, geographical mapping, and network connectivity. A common pitfall is to miss counting all connected components or to count the same component multiple times.
Approach
To solve this problem, we can use Depth-First Search (DFS) or Breadth-First Search (BFS) to explore each island. Here’s a step-by-step approach:
Naive Solution
A naive solution would involve iterating through each cell in the grid and performing a search (DFS or BFS) from each '1' to find the size of the island. However, this approach may lead to redundant searches and is not optimal.
Optimized Solution
An optimized approach involves marking cells as visited once they are part of an island. This prevents redundant searches and ensures each cell is processed only once.
Steps:
- Initialize a list to store the sizes of the islands.
- Iterate through each cell in the grid.
- If a cell contains '1', initiate a DFS/BFS to explore the entire island and count its size.
- Mark all visited cells to avoid recounting.
- Store the size of each island in the list.
Algorithm
We will use DFS for this solution. Here’s a detailed breakdown:
- Initialize a list to store the sizes of the islands.
- Iterate through each cell in the grid.
- If a cell contains '1', initiate a DFS to explore the entire island and count its size.
- Mark all visited cells to avoid recounting.
- Store the size of each island in the list.
Code Implementation
import java.util.*;
public class IslandSizes {
// Directions for moving in the grid
private static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public static List<Integer> findIslandSizes(int[][] grid) {
List<Integer> islandSizes = new ArrayList<>();
int rows = grid.length;
int cols = grid[0].length;
// Iterate through each cell in the grid
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == 1) {
// Start a DFS to find the size of the island
int size = dfs(grid, i, j);
islandSizes.add(size);
}
}
}
return islandSizes;
}
private static int dfs(int[][] grid, int row, int col) {
// Base case: if out of bounds or at a water cell
if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] == 0) {
return 0;
}
// Mark the cell as visited by setting it to 0
grid[row][col] = 0;
int size = 1; // Current cell
// Explore all 4 directions
for (int[] direction : DIRECTIONS) {
size += dfs(grid, row + direction[0], col + direction[1]);
}
return size;
}
public static void main(String[] args) {
int[][] grid1 = {
{1, 1, 1, 1, 0},
{1, 1, 0, 1, 0},
{1, 1, 0, 0, 0},
{0, 0, 0, 0, 0}
};
int[][] grid2 = {
{1, 1, 0, 0, 0},
{1, 1, 0, 0, 0},
{0, 0, 1, 0, 0},
{0, 0, 0, 1, 1}
};
System.out.println(findIslandSizes(grid1)); // Output: [9]
System.out.println(findIslandSizes(grid2)); // Output: [4, 1, 2]
}
}
Complexity Analysis
The time complexity of this 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 in DFS.
Edge Cases
Consider the following edge cases:
- Empty grid: The output should be an empty list.
- Grid with no land: The output should be an empty list.
- Grid with all land: The output should be a single element list with the size of the entire grid.
Testing
To test the solution comprehensively, consider the following test cases:
- Simple grids with one or two islands.
- Grids with no islands.
- Grids with complex shapes of islands.
Use a variety of test cases to ensure the solution handles all scenarios correctly.
Thinking and Problem-Solving Tips
When approaching such problems, consider the following tips:
- Break down the problem into smaller parts.
- Think about edge cases and how to handle them.
- Use visual aids like diagrams to understand the problem better.
- Practice similar problems to improve problem-solving skills.
Conclusion
Understanding and solving problems like finding the size of islands in a grid is crucial for developing strong problem-solving skills. Practice and exploration of different approaches can help in mastering such problems.
Additional Resources
For further reading and practice, consider the following resources:
