Given a 2D grid 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.
Table of Contents
Sample Input:
Grid:
[
['1', '1', '0', '0', '0'],
['1', '1', '0', '0', '0'],
['0', '0', '1', '0', '0'],
['0', '0', '0', '1', '1']
]
Expected Output:
3
In this example, there are three islands in the grid.
Time and Space Complexity:
The time complexity of the algorithm is O(m * n), where ‘m’ is the number of rows and ‘n’ is the number of columns in the grid. We need to visit each cell once to count the number of islands.
The space complexity is O(m * n) as well, due to the recursion stack, which can grow to the size of the grid in the worst case.
C++ solution:
#include <iostream>
#include <vector>
void visitIsland(std::vector<std::vector<char>>& grid, int row, int col) {
// Base case: If the current cell is out of bounds or it is water ('0'), return.
if (row < 0 || row >= grid.size() || col < 0 || col >= grid[0].size() || grid[row][col] == '0') {
return;
}
// Mark the current cell as visited by changing it to water ('0').
grid[row][col] = '0';
// Visit all adjacent cells (top, bottom, left, right) recursively.
visitIsland(grid, row - 1, col); // Top neighbor
visitIsland(grid, row + 1, col); // Bottom neighbor
visitIsland(grid, row, col - 1); // Left neighbor
visitIsland(grid, row, col + 1); // Right neighbor
}
int numIslands(std::vector<std::vector<char>>& grid) {
int numIslands = 0;
// Iterate through the grid to find each island and visit it.
for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid[0].size(); ++j) {
if (grid[i][j] == '1') {
// If the cell is land ('1'), increment the count of islands and visit the island.
numIslands++;
visitIsland(grid, i, j);
}
}
}
return numIslands;
}
int main() {
// Construct the grid for the sample input
std::vector<std::vector<char>> grid = {
{'1', '1', '0', '0', '0'},
{'1', '1', '0', '0', '0'},
{'0', '0', '1', '0', '0'},
{'0', '0', '0', '1', '1'}
};
// Count the number of islands in the grid
int numIslandsCount = numIslands(grid);
// Print the result
std::cout << "Number of Islands: " << numIslandsCount << std::endl;
return 0;
}
The visitIsland function is a helper function that performs a depth-first search (DFS) to visit an island. It starts from a given cell and marks it as visited by changing it to water (‘0’). Then, it recursively visits all its adjacent cells (top, bottom, left, right) that are land (‘1’).
The numIslands function is the entry point of the algorithm, and it iterates through the grid to find each island. Whenever it finds a land (‘1’), it increments the count of islands and calls the visitIsland function to visit the entire island.
In the given example, the function will correctly count the number of islands in the grid, and the output will be 3.