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
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). The 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 cells, which can lead to counting the same island multiple times.
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.
A naive solution would involve checking each cell and its neighbors repeatedly, leading to redundant checks and increased time complexity. This approach is not optimal.
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.
1. Initialize a counter for the number of islands.
2. Iterate through each cell in the grid.
3. When a '1' is found, increment the island counter and initiate a DFS/BFS to mark all connected '1's as visited.
4. Continue until all cells are processed.
public class NumberOfIslands {
// Directions for moving in the grid
private static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int numIslands = 0;
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 a '1' is found, it's part of an island
if (grid[i][j] == '1') {
numIslands++;
// Perform DFS to mark all connected '1's
dfs(grid, i, j);
}
}
}
return numIslands;
}
private void dfs(char[][] grid, int row, int col) {
int rows = grid.length;
int cols = grid[0].length;
// Base case: if out of bounds or at a '0', return
if (row < 0 || row >= rows || col < 0 || col >= cols || grid[row][col] == '0') {
return;
}
// Mark the cell as visited by setting it to '0'
grid[row][col] = '0';
// Explore all four directions
for (int[] direction : DIRECTIONS) {
int newRow = row + direction[0];
int newCol = col + direction[1];
dfs(grid, newRow, newCol);
}
}
public static void main(String[] args) {
NumberOfIslands solution = new NumberOfIslands();
char[][] grid1 = {
{'1', '1', '1', '1', '0'},
{'1', '1', '0', '1', '0'},
{'1', '1', '0', '0', '0'},
{'0', '0', '0', '0', '0'}
};
System.out.println(solution.numIslands(grid1)); // Output: 1
char[][] grid2 = {
{'1', '1', '0', '0', '0'},
{'1', '1', '0', '0', '0'},
{'0', '0', '1', '0', '0'},
{'0', '0', '0', '1', '1'}
};
System.out.println(solution.numIslands(grid2)); // Output: 3
}
}
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. This is because each cell is visited once. The space complexity is O(M*N) in the worst case due to the recursion stack.
Potential edge cases include:
Each of these cases should be tested to ensure the algorithm handles them correctly.
To test the solution comprehensively, include a variety of test cases:
Using a testing framework like JUnit can help automate and manage these tests.
When approaching such problems, it's essential to:
Practicing similar problems and studying algorithms can significantly improve problem-solving skills.
Counting the number of islands in a grid is a classic problem that helps develop skills in graph traversal algorithms like DFS and BFS. Understanding and solving such problems is crucial for improving algorithmic thinking and coding proficiency.
Practice and exploration of further problems are encouraged to deepen understanding and enhance problem-solving abilities.