Number of Islands
Given a 2D binary grid of `"1"`s (land) and `"0"`s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent land cells horizontally or vertically. **Core Insight:** Each time we find an unvisited land cell `"1"`, we have discovered a new island. We then use DFS (or BFS) to mark all cells of that island as visited (by setting them to `"0"`) so we don't count them again. The total number of DFS calls equals the number of islands. **Algorithm:** Iterate over every cell. When `grid[r][c] == "1"`: increment island count, then call `dfs(r, c)`. In `dfs`: if out of bounds or not `"1"` return. Set `grid[r][c] = "0"`. Recurse on all 4 neighbours. **Why mutate the grid:** Marking visited cells as `"0"` in-place avoids a separate `visited` array. If the input must not be modified, use a boolean visited matrix instead. **Complexity:** Time O(m × n) — each cell is visited at most once. Space O(m × n) — recursion stack.
Constraints
- •
m == grid.length - •
n == grid[i].length - •
1 ≤ m, n ≤ 300
def numIslands(grid: list[list[str]]) -> int:
def dfs(r, c):
if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]) or grid[r][c] != '1': return
grid[r][c] = '0'
dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1)
count = 0
for r in range(len(grid)):
for c in range(len(grid[0])):
if grid[r][c] == '1':
dfs(r, c)
count += 1
return count