200. Number of Islands - cocoder39/coco39_LC GitHub Wiki
Notes 2022
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
m, n = len(grid), len(grid[0])
visited = [[False for _ in range(n)] for _ in range(m)]
number = 0
for i in range(m):
for j in range(n):
if grid[i][j] == '1' and not visited[i][j]:
number += 1
visited[i][j] = True
self.__mark_connected_islands(grid, visited, i, j)
return number
# use DFS to mark connected islands
def __mark_connected_islands(self, grid: List[List[str]], visited: List[List[bool]], row: int, col: int) -> None:
delta = [(-1, 0), (1, 0), (0, -1), (0, 1)]
m, n = len(grid), len(grid[0])
for dx, dy in delta:
if 0 <= row + dx < m and 0 <= col + dy < n and grid[row+dx][col+dy] == '1' and not visited[row+dx][col+dy]:
visited[row+dx][col+dy] = True
self.__mark_connected_islands(grid, visited, row+dx, col+dy)
==============================================================================
time complexity is O(m * n) and space complexity is O(1).
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int m = grid.size();
if (m == 0) {
return 0;
}
int n = grid[0].size();
int num = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
num++;
helper(grid, m, n, i, j);
}
}
}
for (int i = 0; i < m; i++) { // recovery
for (int j = 0; j < n; j++) {
if (grid[i][j] == '3') {
grid[i][j] = '1';
}
}
}
return num;
}
void helper(vector<vector<char>> &grid, int m, int n, int row, int col) {
grid[row][col] = '3';
static const vector<vector<int>> dirs{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (auto dir : dirs) {
int r = row + dir[0];
int c = col + dir[1];
if (r >= 0 && r < m && c >= 0 && c < n && grid[r][c] == '1') {
helper(grid, m, n, r, c);
}
}
}
};