# Number of Islands

- **Canonical ID**: `number-of-islands`
- **Canonical URL**: https://dsacheatsheet.com/problems/number-of-islands
- **Difficulty**: medium
- **Patterns**: Graphs
- **Version**: 1.0.0 (verified 2026-11-11T21:20:00Z)
- **Original Problem**: https://leetcode.com/problems/number-of-islands/

## 1. Core Invariant / The Trick

Iterate every cell `(r, c)`. Whenever `grid[r][c] == "1"`, increment `islands` and immediately flood-fill (DFS/BFS) all 4-connected `"1"` cells to `"0"` in-place so each component is counted once.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(M * N)`
- **Space Complexity**: `O(M * N)`
- **Proof**: Each cell is marked visited at most once; worst-case DFS recursion/BFS queue holds all M*N cells.

## 3. Minimal Idiomatic Code

### Python
```python
def numIslands(grid: list[list[str]]) -> int:
    R, C = len(grid), len(grid[0])
    ans = 0
    for r in range(R):
        for c in range(C):
            if grid[r][c] == '1':
                ans += 1
                grid[r][c] = '0'
                q = deque([(r, c)])
                while q:
                    cr, cc = q.popleft()
                    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                        nr, nc = cr + dr, cc + dc
                        if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == '1':
                            grid[nr][nc] = '0'
                            q.append((nr, nc))
    return ans
```

### TypeScript
```typescript
export function numIslands(grid: string[][]): number {
  const R = grid.length, C = grid[0].length;
  let ans = 0;
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  for (let r = 0; r < R; r++) {
    for (let c = 0; c < C; c++) {
      if (grid[r][c] === '1') {
        ans++;
        grid[r][c] = '0';
        const q: Array<[number, number]> = [[r, c]];
        while (q.length > 0) {
          const [cr, cc] = q.shift()!;
          for (const [dr, dc] of dirs) {
            const nr = cr + dr, nc = cc + dc;
            if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] === '1') {
              grid[nr][nc] = '0';
              q.push([nr, nc]);
            }
          }
        }
      }
    }
  }
  return ans;
}
```

### C++
```cpp
int numIslands(vector<vector<char>>& grid) {
    int R = grid.size(), C = grid[0].size(), ans = 0;
    auto dfs = [&](auto& self, int r, int c) -> void {
        if (r < 0 || r >= R || c < 0 || c >= C || grid[r][c] != '1') return;
        grid[r][c] = '0';
        self(self, r+1, c); self(self, r-1, c); self(self, r, c+1); self(self, r, c-1);
    };
    for (int r = 0; r < R; ++r)
        for (int c = 0; c < C; ++c)
            if (grid[r][c] == '1') { ans++; dfs(dfs, r, c); }
    return ans;
}
```

### Java
```java
int numIslands(char[][] grid) {
    int R = grid.length, C = grid[0].length, ans = 0;
    for (int r = 0; r < R; r++)
        for (int c = 0; c < C; c++)
            if (grid[r][c] == '1') { ans++; sink(grid, r, c); }
    return ans;
}
void sink(char[][] g, int r, int c) {
    if (r < 0 || r >= g.length || c < 0 || c >= g[0].length || g[r][c] != '1') return;
    g[r][c] = '0';
    sink(g, r+1, c); sink(g, r-1, c); sink(g, r, c+1); sink(g, r, c-1);
}
```

### Go
```go
func numIslands(grid [][]byte) int {
    R, C, ans := len(grid), len(grid[0]), 0
    var dfs func(int, int)
    dfs = func(r, c int) {
        if r < 0 || r >= R || c < 0 || c >= C || 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)
    }
    for r := 0; r < R; r++ {
        for c := 0; c < C; c++ {
            if grid[r][c] == '1' { ans++; dfs(r, c) }
        }
    }
    return ans
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Marking visited upon *popping* from BFS queue instead of before *pushing* causes exponential duplicate enqueues.
- Using BFS uses O(min(M, N)) queue memory vs O(M*N) call stack in worst-case spiral DFS.

### Follow-ups
- Dynamic islands added online: use Union-Find on `(r * cols + c)` grid indices.