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
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.
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:
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.
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.
We will use DFS for this solution. Here’s a detailed breakdown:
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]
}
}
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.
Consider the following edge cases:
To test the solution comprehensively, consider the following test cases:
Use a variety of test cases to ensure the solution handles all scenarios correctly.
When approaching such problems, consider the following tips:
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.
For further reading and practice, consider the following resources: