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}Java solution employs a private DFS helper function that mutates the grid to mark visited nodes. On finding a '1', we increment the island count and initiate DFS to visit the island fully.
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.
1from collections import deque
2
3class Solution:
4 def numIslands(self, grid):
5 if not grid:
6 return 0
7 num_islands = 0
8 rows, cols = len(grid), len(grid[0])
9
10 def bfs(r, c):
11 queue = deque([(r, c)])
12 grid[r][c] = '0'
13 directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
14 while queue:
15 cr, cc = queue.popleft()
16 for dr, dc in directions:
17 nr, nc = cr + dr, cc + dc
18 if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
19 grid[nr][nc] = '0'
20 queue.append((nr, nc))
21
22 for r in range(rows):
23 for c in range(cols):
24 if grid[r][c] == '1':
25 num_islands += 1
26 bfs(r, c)
27 return num_islandsThe Python implementation employs the collections.deque to perform BFS. Upon encountering a '1', the coordinates are queued and BFS enqueues its adjacent lands, effectively exploring the entire island and marking progress.