Number of Islands
Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return 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.
Constraints:
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 200
- grid[i][j] is '1' or '0'
Examples:
Input: [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]
Output: 1
Explanation: There is only one island in the grid, which is the entire grid itself.
Input: [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]
Output: 3
Explanation: There are three islands in the grid: one in the top left, one in the bottom left, and one in the bottom right.
Solutions
Depth-First Search
The solution uses a depth-first search (DFS) approach to traverse the grid and count the number of islands. The DFS function is called for each cell in the grid that contains a '1', which represents land. The DFS function then marks all adjacent land cells as visited by setting them to '0', and recursively calls itself for each adjacent land cell. The count of islands is incremented each time a new island is found.
function numIslands(grid) {
let count = 0;
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[0].length; j++) {
if (grid[i][j] === '1') {
dfs(grid, i, j);
count++;
}
}
}
return count;
function dfs(grid, i, j) {
if (
i < 0 ||
j < 0 ||
i >= grid.length ||
j >= grid[0].length ||
grid[i][j] !== '1'
)
return;
grid[i][j] = '0';
dfs(grid, i - 1, j);
dfs(grid, i + 1, j);
dfs(grid, i, j - 1);
dfs(grid, i, j + 1);
}
}
Follow-up:
How would you solve this problem if the grid is very large and does not fit into memory?
