Sponsored
Sponsored
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.
1class Solution:
2 def dfs(self, grid, r, c):
3 if r < 0 or c < 0 or r >= len(grid) or c >= len(grid[0]) or grid[r][c] == '0':
4 return
5 grid[r][c] = '0'
6 self.dfs(grid, r-1, c)
7 self.dfs(grid, r+1, c)
8 self.dfs(grid, r, c-1)
9 self.dfs(grid, r, c+1)
10
11 def numIslands(self, grid):
12 if not grid:
13 return 0
14 num_islands = 0
15 for r in range(len(grid)):
16 for c in range(len(grid[0])):
17 if grid[r][c] == '1':
18 num_islands += 1
19 self.dfs(grid, r, c)
20 return num_islandsPython's solution uses a method dfs to explore and mark connected lands. We iterate over the entire grid, and for every '1' encountered, initiate a DFS from that position, effectively exploring the whole island.
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
The 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.