This approach uses Depth-First Search (DFS) to explore the grid. We iterate over each cell in the grid, and every time we find an unvisited '1', it indicates the discovery of a new island. We then perform DFS from that cell to mark all the connected '1's as visited, effectively marking the entire island.
Time Complexity: O(m*n) where m is the number of rows and n is the number of columns since each cell is visited once.
Space Complexity: O(m*n) in the worst case due to the recursion stack used by DFS.
1var numIslands = function(grid) {
2 function dfs(grid, r, c) {
3 if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] === '0') {
4 return;
5 }
6 grid[r][c] = '0';
7 dfs(grid, r-1, c);
8 dfs(grid, r+1, c);
9 dfs(grid, r, c-1);
10 dfs(grid, r, c+1);
11 }
12 let numIslands = 0;
13 for (let r = 0; r < grid.length; r++) {
14 for (let c = 0; c < grid[0].length; c++) {
15 if (grid[r][c] === '1') {
16 numIslands++;
17 dfs(grid, r, c);
18 }
19 }
20 }
21 return numIslands;
22};The JavaScript solution leverages a classic DFS function dfs to explore the grid and perform in-place modification to mark visited cells. As it iterates through the grid, whenever it encounters '1', it initiates DFS to mark the whole island, counting it.
This approach uses Breadth-First Search (BFS) to traverse the grid. Similar to DFS, we treat each '1' as a node in a graph. On encountering a '1', we initiate a BFS to explore all connected '1's (island nodes) by utilizing a queue for the frontier, marking them in-place as visited.
Time Complexity: O(m*n), where m and n are rows and columns.#
Space Complexity: O(min(m, n)) due to the queue storage in BFS.
1import java.util.LinkedList;
2import java.util.Queue;
3
4public class Solution {
5 private static final int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
6
7 public int numIslands(char[][] grid) {
8 if (grid == null || grid.length == 0) {
9 return 0;
10 }
11 int numIslands = 0;
12 for (int r = 0; r < grid.length; r++) {
13 for (int c = 0; c < grid[0].length; c++) {
14 if (grid[r][c] == '1') {
15 numIslands++;
16 grid[r][c] = '0';
17 Queue<int[]> queue = new LinkedList<>();
18 queue.add(new int[]{r, c});
19 while (!queue.isEmpty()) {
20 int[] cell = queue.poll();
21 for (int[] d : directions) {
22 int nr = cell[0] + d[0], nc = cell[1] + d[1];
23 if (nr >= 0 && nr < grid.length && nc >= 0 && nc < grid[0].length && grid[nr][nc] == '1') {
24 queue.add(new int[]{nr, nc});
25 grid[nr][nc] = '0';
26 }
27 }
28 }
29 }
30 }
31 }
32 return numIslands;
33 }
34}Java's solution leverages a Queue to implement BFS. When encountering '1', BFS starts and expands, visiting the whole component marking each cell and exploring adjacent '1's iteratively using the queue.