# 200. Number of Islands

## Approach 1: BFS

• Time: $O(mn)$
• Space: $O(\min(m, n))$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class Solution { public: int numIslands(vector>& grid) { const int m = grid.size(); const int n = grid[0].size(); const vector dirs{0, 1, 0, -1, 0}; int ans = 0; auto bfs = [&](int r, int c) { queue> q{{{r, c}}}; grid[r][c] = '2'; // mark '2' as visited while (!q.empty()) { const auto [i, j] = q.front(); q.pop(); for (int k = 0; k < 4; ++k) { const int x = i + dirs[k]; const int y = j + dirs[k + 1]; if (x < 0 || x == m || y < 0 || y == n) continue; if (grid[x][y] != '1') continue; q.emplace(x, y); grid[x][y] = '2'; // mark '2' as visited } } }; for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) if (grid[i][j] == '1') { bfs(i, j); ++ans; } return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 class Solution { public int numIslands(char[][] grid) { int ans = 0; for (int i = 0; i < grid.length; ++i) for (int j = 0; j < grid[0].length; ++j) if (grid[i][j] == '1') { bfs(grid, i, j); ++ans; } return ans; } private static final int[] dirs = {0, 1, 0, -1, 0}; private void bfs(char[][] grid, int r, int c) { Queue q = new ArrayDeque<>(); q.offer(new int[] {r, c}); grid[r][c] = '2'; // mark '2' as visited while (!q.isEmpty()) { final int i = q.peek()[0]; final int j = q.poll()[1]; for (int k = 0; k < 4; ++k) { final int x = i + dirs[k]; final int y = j + dirs[k + 1]; if (x < 0 || x == grid.length || y < 0 || y == grid[0].length) continue; if (grid[x][y] != '1') continue; q.offer(new int[] {x, y}); grid[x][y] = '2'; // mark '2' as visited } } } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution: def numIslands(self, grid: List[List[str]]) -> int: m = len(grid) n = len(grid[0]) dirs = [0, 1, 0, -1, 0] def bfs(r, c): q = deque([(r, c)]) grid[r][c] = '2' # mark '2' as visited while q: i, j = q.popleft() for k in range(4): x = i + dirs[k] y = j + dirs[k + 1] if x < 0 or x == m or y < 0 or y == n: continue if grid[x][y] != '1': continue q.append((x, y)) grid[x][y] = '2' # mark '2' as visited ans = 0 for i in range(m): for j in range(n): if grid[i][j] == '1': bfs(i, j) ans += 1 return ans 

## Approach 2: DFS

• Time: $O(mn)$
• Space: $O(mn)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 class Solution { public: int numIslands(vector>& grid) { int ans = 0; for (int i = 0; i < grid.size(); ++i) for (int j = 0; j < grid[0].size(); ++j) if (grid[i][j] == '1') { dfs(grid, i, j); ++ans; } return ans; } private: void dfs(vector>& grid, int i, int j) { if (i < 0 || i == grid.size() || j < 0 || j == grid[0].size()) return; if (grid[i][j] != '1') return; grid[i][j] = '2'; // mark '2' as visited dfs(grid, i + 1, j); dfs(grid, i - 1, j); dfs(grid, i, j + 1); dfs(grid, i, j - 1); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution { public int numIslands(char[][] grid) { int ans = 0; for (int i = 0; i < grid.length; ++i) for (int j = 0; j < grid[0].length; ++j) if (grid[i][j] == '1') { dfs(grid, i, j); ++ans; } return ans; } private void dfs(char[][] grid, int i, int j) { if (i < 0 || i == grid.length || j < 0 || j == grid[0].length) return; if (grid[i][j] != '1') return; grid[i][j] = '2'; // mark '2' as visited dfs(grid, i + 1, j); dfs(grid, i - 1, j); dfs(grid, i, j + 1); dfs(grid, i, j - 1); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution: def numIslands(self, grid: List[List[str]]) -> int: m = len(grid) n = len(grid[0]) def dfs(i: int, j: int) -> None: if i < 0 or i == m or j < 0 or j == n: return if grid[i][j] != '1': return grid[i][j] = '2' # mark '2' as visited dfs(i + 1, j) dfs(i - 1, j) dfs(i, j + 1) dfs(i, j - 1) ans = 0 for i in range(m): for j in range(n): if grid[i][j] == '1': dfs(i, j) ans += 1 return ans