Problem
Given an m × n grid of'1's and '0's, where '1' represents land and '0' represents water, return the number of islands.
An island is formed by connecting adjacent land cells horizontally or vertically. You may assume that all four edges of the grid are surrounded by water.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
grid = [
['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']
]
0 1 2 3 4
+---+---+---+---+---+
0 | 1 | 1 | 0 | 0 | 0 |
+---+---+---+---+---+
1 | 1 | 1 | 0 | 0 | 0 |
+---+---+---+---+---+
2 | 0 | 0 | 1 | 0 | 0 |
+---+---+---+---+---+
3 | 0 | 0 | 0 | 1 | 1 |
+---+---+---+---+---+
Output
3 Solution
This solution uses Depth-First Search (DFS). We traverse every cell in the grid and look for unvisited land represented by'1'.
Whenever a
'1' is found, it represents a new island, so the island count is increased. We then use DFS to visit all horizontally and vertically connected land cells belonging to that island.
Each visited land cell is changed to
'0' so that it is not processed again. Once DFS finishes, the entire island has been visited, and the traversal continues to search for the next island.
public int numIslands(char[][] grid) {
int islands = 0;
for (int row = 0; row < grid.length; row++) {
for (int col = 0; col < grid[0].length; col++) {
// Found a new island.
if (grid[row][col] == '1') {
islands++;
dfs(grid, row, col);
}
}
}
return islands;
}
private void dfs(char[][] grid, int row, int col) {
// Stop at boundaries or water.
if (row < 0 || row >= grid.length
|| col < 0 || col >= grid[0].length
|| grid[row][col] == '0') {
return;
}
// Mark the current land as visited.
grid[row][col] = '0';
dfs(grid, row + 1, col);
dfs(grid, row - 1, col);
dfs(grid, row, col + 1);
dfs(grid, row, col - 1);
}
Complexity
Each cell is visited at most once, resulting in a time complexity ofO(m × n). In the worst case, the recursive DFS call stack can contain all land cells, requiring O(m × n) extra space.