In this problem, we are given a 2D grid consisting of ‘1’s (land) and ‘0’s (water). Our task is to count the number of islands. An island consists of a group of connected ‘1’s surrounded by water (‘0’s). The connection can be in four directions—up, down, left, or right.
The most important aspect of this problem is to ensure that we count each piece of land only once. To do this, we need an efficient way to traverse the grid and mark visited lands.
Input:
grid = [
['1', '1', '0', '0', '0'],
['1', '1', '0', '0', '0'],
['0', '0', '1', '0', '0'],
['0', '0', '0', '1', '1']
]
Output: 3
Explanation:
- The first two rows form one island.
- The single '1' in the third row is another island.
- The last two '1's in the fourth row form the third island.
Brute Force Approach
A naive approach would be to iterate over every cell in the grid and try to count islands while keeping track of visited cells using an auxiliary data structure. This method would involve unnecessary re-traversals, making it inefficient.
Steps:
- Initialize a variable
countto store the number of islands. - Create a separate
visitedmatrix to track visited cells. - Iterate through every cell in the grid:
- Return
countas the number of islands.
Optimized Approach
Instead of maintaining an extra visited array, we can modify the grid itself by marking visited land cells as ‘0’ (water). This reduces space complexity while ensuring we don’t count the same island multiple times.
Steps:
- Initialize
count = 0to track the number of islands. - Iterate through the grid:
- If a cell is ‘1’, trigger a Depth-First Search (DFS) to mark all connected land as visited.
- Increment
countafter each DFS traversal.
- The DFS function should:
- Check if the cell is out of bounds or already water (‘0’). If so, return.
- Mark the current cell as ‘0’ to avoid re-visiting.
- Recursively visit its neighbors (up, down, left, right).
- Once the entire grid is traversed, return
count.
Code:
int numIslands(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int count = 0;
for (int i = 0; i < grid.length; i++)
for (int j = 0; j < grid[0].length; j++)
if (grid[i][j] == '1') {
dfs(grid, i, j);
count++;
}
return count;
}
private void dfs(char[][] grid, int i, int j) {
if (i < 0 || i >= grid.length
|| j < 0 || j >= grid[0].length
|| grid[i][j] == '0') {
return;
}
grid[i][j] = '0'; // Mark the cell as visited
// Explore all four directions
dfs(grid, i + 1, j);
dfs(grid, i - 1, j);
dfs(grid, i, j + 1);
dfs(grid, i, j - 1);
}
Code language: Java (java)- Time Complexity: O(n * m), where
nis the number of rows andmis the number of columns. Each cell is visited once and its adjacent cells are checked at most once. - Space Complexity: O(n * m) in the worst case due to recursion stack depth (if the grid is entirely land). However, this is more space-efficient than using an auxiliary visited array.
Video Explanation:
