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.
1public class Solution {
2 private void Dfs(char[][] grid, int r, int 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
13 public int NumIslands(char[][] grid) {
14 if (grid == null || grid.Length == 0) {
15 return 0;
16 }
17 int numIslands = 0;
18 for (int i = 0; i < grid.Length; i++) {
19 for (int j = 0; j < grid[i].Length; j++) {
20 if (grid[i][j] == '1') {
21 numIslands++;
22 Dfs(grid, i, j);
23 }
24 }
25 }
26 return numIslands;
27 }
28}C# uses a recursive DFS strategy analogous to other languages. We traverse the grid and incite DFS when encountering '1's, marking entire islands as visited in the process.
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.
1var numIslands = function(grid) {
2 if (!grid.length) return 0;
3 let numIslands = 0;
4 const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
5 const bfs = function(r, c) {
6 const queue = [];
7 queue.push([r, c]);
8 grid[r][c] = '0';
9 while (queue.length) {
10 const [cr, cc] = queue.shift();
11 for (const [dr, dc] of directions) {
12 const nr = cr + dr;
13 const nc = cc + dc;
14 if (nr >= 0 && nr < grid.length && nc >= 0 && nc < grid[0].length && grid[nr][nc] === '1') {
15 queue.push([nr, nc]);
16 grid[nr][nc] = '0';
17 }
18 }
19 }
20 };
21 for (let r = 0; r < grid.length; r++) {
22 for (let c = 0; c < grid[0].length; c++) {
23 if (grid[r][c] === '1') {
24 numIslands++;
25 bfs(r, c);
26 }
27 }
28 }
29 return numIslands;
30};The JavaScript BFS-based solution leverages an array queue to coordinate BFS execution over the identified grid. It proceeds to mark the entire island upon encountering a '1' by iteratively fetching and exploring its potential connections.