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.
1#include <stdbool.h>
2#include <stdlib.h>
3#include <assert.h>
4
5typedef struct {
6 int r, c;
7} QueueNode;
8
9void bfs(char** grid, int gridSize, int* gridColSize, int sr, int sc) {
10 QueueNode* queue = malloc(gridSize * gridSize * sizeof(QueueNode)); // Worst case memory
11 int front = 0, rear = 0;
12 queue[rear++] = (QueueNode){sr, sc};
13 while (front < rear) {
14 QueueNode node = queue[front++];
15 int dr[4] = {-1, 1, 0 , 0};
16 int dc[4] = {0, 0, -1, 1};
17 for (int i = 0; i < 4; i++) {
18 int r = node.r + dr[i], c = node.c + dc[i];
19 if (r < 0 || c < 0 || r >= gridSize || c >= gridColSize[r] || grid[r][c] == '0') {
20 continue;
21 }
22 grid[r][c] = '0';
23 queue[rear++] = (QueueNode){r, c};
24 }
25 }
26 free(queue);
27}
28
29int numIslands(char** grid, int gridSize, int* gridColSize) {
30 int numIslands = 0;
31 for (int i = 0; i < gridSize; i++) {
32 for (int j = 0; j < gridColSize[i]; j++) {
33 if (grid[i][j] == '1') {
34 numIslands++;
35 bfs(grid, gridSize, gridColSize, i, j);
36 }
37 }
38 }
39 return numIslands;
40}This C implementation utilizes a queue for BFS to explore and mark connected components of each found '1'. An auxiliary structure QueueNode is used to keep track of cell indices being explored. BFS propagates through the nodes layer by layer until the entire island is marked.